const_div.hpp

Go to the documentation of this file.

/*
 * Copyright (c) 2014-2015, Hewlett-Packard Development Company, LP.
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the Free
 * Software Foundation; either version 2 of the License, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
 * more details. You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
 *
 * HP designates this particular file as subject to the "Classpath" exception
 * as provided by HP in the LICENSE.txt file that accompanied this code.
 */
#ifndef FOEDUS_ASSORTED_CONST_DIV_HPP_
#define FOEDUS_ASSORTED_CONST_DIV_HPP_
#include <stdint.h>

#include "foedus/assert_nd.hpp"
#include "foedus/cxx11.hpp"

namespace foedus {
namespace assorted {
const uint32_t kPower2To31 = 1U << 31;
const uint64_t kPower2To63 = 1ULL << 63;
const uint32_t kFull32Bits = 0xFFFFFFFF;
const uint32_t kFull31Bits = 0x7FFFFFFF;
const uint64_t kFull64Bits = 0xFFFFFFFFFFFFFFFFULL;
const uint64_t kFull63Bits = 0x7FFFFFFFFFFFFFFFULL;

struct ConstDiv {
  enum Constants {
    kFlagPowerOfTwo = 0x01,
    kFlagAdd32 = 0x02,
    kFlagAdd64 = 0x04,
  };

  explicit ConstDiv(uint32_t d) {
    init(d);
  }

  ConstDiv() {
    init(1);
  }

  void init(uint32_t d);

  uint32_t div32(uint32_t n) const;
  uint32_t rem32(uint32_t n, uint32_t d, uint32_t q) const;

  uint64_t div64(uint64_t n) const;
  uint32_t rem64(uint64_t n, uint32_t d, uint64_t q) const;

  uint8_t d_highest_bits_;  // +1 => 1

  uint8_t shift32_;  // +1 => 2

  uint8_t shift64_;  // +1 => 3

  uint8_t flags_;  // +1 => 4

  uint32_t magic32_;  // +4 => 8

  uint64_t magic64_;  // +8 => 16

#ifndef NDEBUG

  uint32_t d_;
  uint32_t dummy_;
#endif  // NDEBUG
};

inline void ConstDiv::init(uint32_t d) {
  // this one is inlined just to avoid multiple-definition, not for performance.
  ASSERT_ND(d);
  d_highest_bits_ = 31 - __builtin_clz(d);  // TASK(Hideaki): non-GCC support
#ifndef NDEBUG
  d_ = d;
  dummy_ = 0;
#endif  // NDEBUG

  // power of 2 is a bit special.
  if ((d & (d - 1)) == 0) {
    ASSERT_ND(d == (1U << d_highest_bits_));
    shift32_ = 0;
    shift64_ = 0;
    flags_ = kFlagPowerOfTwo;
    magic32_ = 0;
    magic64_ = 0;
    return;
  }

  flags_ = 0;

  // calculate 32bit/64bit magic numbers and add indicator, this part is based on [libdivide-pdf]
  // rather than [HACKERS] although it is also based on [HACKERS].
  {
    shift32_ = d_highest_bits_;
    uint32_t m = (1ULL << (32 + d_highest_bits_)) / d;
    uint32_t rem = (1ULL << (32 + d_highest_bits_)) % d;
    ASSERT_ND(rem > 0 && rem < d);
    uint32_t e = d - rem;
    if (e >= (1U << d_highest_bits_)) {
      // we have add indicator (2^W <= M < 2^(W+1), m = M - 2^W).
      // here is a nice idea in libdivide.
      // We let it overflow, but we do so for remainder too, thus even with overflow
      // we can correctly calculate the quotient!
      // We use the magic number for this case with divide-by-2 in div32 to account for this.
      flags_ |= kFlagAdd32;
      m *= 2;
      uint32_t twice_rem = rem * 2;
      if (twice_rem >= d || twice_rem < rem) {
        ++m;
      }
    }
    magic32_ = m + 1;
  }

  // then 64bit version.
  {
    shift64_ = d_highest_bits_;
    // At least GCC and clang supports __uint128_t
    __uint128_t numer = 1;
    numer <<= 64 + d_highest_bits_;
    uint64_t m = numer / d;
    uint32_t rem = numer % d;
    ASSERT_ND(rem > 0 && rem < d);
    uint32_t e = d - rem;
    if (e >= (1ULL << d_highest_bits_)) {
      flags_ |= kFlagAdd64;
      m *= 2;
      uint32_t twice_rem = rem * 2;
      if (twice_rem >= d || twice_rem < rem) {
        ++m;
      }
    }
    magic64_ = m + 1;
  }
}

inline uint32_t ConstDiv::rem32(uint32_t n, uint32_t d, uint32_t q) const {
#ifndef NDEBUG
  ASSERT_ND(d == d_);
#endif  // NDEBUG
  ASSERT_ND(n / d == q);
  if (flags_ & kFlagPowerOfTwo) {
    return n & ((1 << d_highest_bits_) - 1);
  } else {
    return n - d * q;
  }
}
inline uint32_t ConstDiv::rem64(uint64_t n, uint32_t d, uint64_t q) const {
#ifndef NDEBUG
  ASSERT_ND(d == d_);
#endif  // NDEBUG
  ASSERT_ND(n / d == q);
  if (flags_ & kFlagPowerOfTwo) {
    return n & ((1ULL << d_highest_bits_) - 1ULL);
  } else {
    return n - d * q;
  }
}

inline uint32_t ConstDiv::div32(uint32_t n) const {
  if (flags_ & kFlagPowerOfTwo) {
    return n >> d_highest_bits_;
  } else {
    uint64_t product = static_cast<uint64_t>(n) * magic32_;
    uint32_t quotient = static_cast<uint32_t>(product >> 32);
    if (flags_ & kFlagAdd32) {
      quotient += (n - quotient) >> 1;
    }
    return quotient >> shift32_;
  }
}

inline uint64_t ConstDiv::div64(uint64_t n) const {
  if (flags_ & kFlagPowerOfTwo) {
    return n >> d_highest_bits_;
  }

  if (n < (1ULL << 32)) {
    // cheap case
    return div32(static_cast<uint32_t>(n));
  }

  ASSERT_ND(n >= (1ULL << 32));
  // At least GCC and clang supports __uint128_t
  __uint128_t product = static_cast<__uint128_t>(n) * magic64_;
  uint64_t quotient = static_cast<uint64_t>(product >> 64);
  if (flags_ & kFlagAdd64) {
    quotient += (n - quotient) >> 1;
  }
  return quotient >> shift64_;
}

}  // namespace assorted
}  // namespace foedus
#endif  // FOEDUS_ASSORTED_CONST_DIV_HPP_