Source file src/math/bits/bits.go

     1  // Copyright 2017 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  //go:generate go run make_tables.go
     6  
     7  // Package bits implements bit counting and manipulation
     8  // functions for the predeclared unsigned integer types.
     9  //
    10  // Functions in this package may be implemented directly by
    11  // the compiler, for better performance. For those functions
    12  // the code in this package will not be used. Which
    13  // functions are implemented by the compiler depends on the
    14  // architecture and the Go release.
    15  package bits
    16  
    17  const uintSize = 32 << (^uint(0) >> 63) // 32 or 64
    18  
    19  // UintSize is the size of a uint in bits.
    20  const UintSize = uintSize
    21  
    22  // --- LeadingZeros ---
    23  
    24  // LeadingZeros returns the number of leading zero bits in x; the result is [UintSize] for x == 0.
    25  func LeadingZeros(x uint) int { return UintSize - Len(x) }
    26  
    27  // LeadingZeros8 returns the number of leading zero bits in x; the result is 8 for x == 0.
    28  func LeadingZeros8(x uint8) int { return 8 - Len8(x) }
    29  
    30  // LeadingZeros16 returns the number of leading zero bits in x; the result is 16 for x == 0.
    31  func LeadingZeros16(x uint16) int { return 16 - Len16(x) }
    32  
    33  // LeadingZeros32 returns the number of leading zero bits in x; the result is 32 for x == 0.
    34  func LeadingZeros32(x uint32) int { return 32 - Len32(x) }
    35  
    36  // LeadingZeros64 returns the number of leading zero bits in x; the result is 64 for x == 0.
    37  func LeadingZeros64(x uint64) int { return 64 - Len64(x) }
    38  
    39  // --- TrailingZeros ---
    40  
    41  // See http://supertech.csail.mit.edu/papers/debruijn.pdf
    42  const deBruijn32 = 0x077CB531
    43  
    44  var deBruijn32tab = [32]byte{
    45  	0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    46  	31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
    47  }
    48  
    49  const deBruijn64 = 0x03f79d71b4ca8b09
    50  
    51  var deBruijn64tab = [64]byte{
    52  	0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
    53  	62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
    54  	63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
    55  	54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
    56  }
    57  
    58  // TrailingZeros returns the number of trailing zero bits in x; the result is [UintSize] for x == 0.
    59  func TrailingZeros(x uint) int {
    60  	if UintSize == 32 {
    61  		return TrailingZeros32(uint32(x))
    62  	}
    63  	return TrailingZeros64(uint64(x))
    64  }
    65  
    66  // TrailingZeros8 returns the number of trailing zero bits in x; the result is 8 for x == 0.
    67  func TrailingZeros8(x uint8) int {
    68  	return int(ntz8tab[x])
    69  }
    70  
    71  // TrailingZeros16 returns the number of trailing zero bits in x; the result is 16 for x == 0.
    72  func TrailingZeros16(x uint16) int {
    73  	if x == 0 {
    74  		return 16
    75  	}
    76  	// see comment in TrailingZeros64
    77  	return int(deBruijn32tab[uint32(x&-x)*deBruijn32>>(32-5)])
    78  }
    79  
    80  // TrailingZeros32 returns the number of trailing zero bits in x; the result is 32 for x == 0.
    81  func TrailingZeros32(x uint32) int {
    82  	if x == 0 {
    83  		return 32
    84  	}
    85  	// see comment in TrailingZeros64
    86  	return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)])
    87  }
    88  
    89  // TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0.
    90  func TrailingZeros64(x uint64) int {
    91  	if x == 0 {
    92  		return 64
    93  	}
    94  	// If popcount is fast, replace code below with return popcount(^x & (x - 1)).
    95  	//
    96  	// x & -x leaves only the right-most bit set in the word. Let k be the
    97  	// index of that bit. Since only a single bit is set, the value is two
    98  	// to the power of k. Multiplying by a power of two is equivalent to
    99  	// left shifting, in this case by k bits. The de Bruijn (64 bit) constant
   100  	// is such that all six bit, consecutive substrings are distinct.
   101  	// Therefore, if we have a left shifted version of this constant we can
   102  	// find by how many bits it was shifted by looking at which six bit
   103  	// substring ended up at the top of the word.
   104  	// (Knuth, volume 4, section 7.3.1)
   105  	return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)])
   106  }
   107  
   108  // --- OnesCount ---
   109  
   110  const m0 = 0x5555555555555555 // 01010101 ...
   111  const m1 = 0x3333333333333333 // 00110011 ...
   112  const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
   113  const m3 = 0x00ff00ff00ff00ff // etc.
   114  const m4 = 0x0000ffff0000ffff
   115  
   116  // OnesCount returns the number of one bits ("population count") in x.
   117  func OnesCount(x uint) int {
   118  	if UintSize == 32 {
   119  		return OnesCount32(uint32(x))
   120  	}
   121  	return OnesCount64(uint64(x))
   122  }
   123  
   124  // OnesCount8 returns the number of one bits ("population count") in x.
   125  func OnesCount8(x uint8) int {
   126  	return int(pop8tab[x])
   127  }
   128  
   129  // OnesCount16 returns the number of one bits ("population count") in x.
   130  func OnesCount16(x uint16) int {
   131  	return int(pop8tab[x>>8] + pop8tab[x&0xff])
   132  }
   133  
   134  // OnesCount32 returns the number of one bits ("population count") in x.
   135  func OnesCount32(x uint32) int {
   136  	return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
   137  }
   138  
   139  // OnesCount64 returns the number of one bits ("population count") in x.
   140  func OnesCount64(x uint64) int {
   141  	// Implementation: Parallel summing of adjacent bits.
   142  	// See "Hacker's Delight", Chap. 5: Counting Bits.
   143  	// The following pattern shows the general approach:
   144  	//
   145  	//   x = x>>1&(m0&m) + x&(m0&m)
   146  	//   x = x>>2&(m1&m) + x&(m1&m)
   147  	//   x = x>>4&(m2&m) + x&(m2&m)
   148  	//   x = x>>8&(m3&m) + x&(m3&m)
   149  	//   x = x>>16&(m4&m) + x&(m4&m)
   150  	//   x = x>>32&(m5&m) + x&(m5&m)
   151  	//   return int(x)
   152  	//
   153  	// Masking (& operations) can be left away when there's no
   154  	// danger that a field's sum will carry over into the next
   155  	// field: Since the result cannot be > 64, 8 bits is enough
   156  	// and we can ignore the masks for the shifts by 8 and up.
   157  	// Per "Hacker's Delight", the first line can be simplified
   158  	// more, but it saves at best one instruction, so we leave
   159  	// it alone for clarity.
   160  	const m = 1<<64 - 1
   161  	x = x>>1&(m0&m) + x&(m0&m)
   162  	x = x>>2&(m1&m) + x&(m1&m)
   163  	x = (x>>4 + x) & (m2 & m)
   164  	x += x >> 8
   165  	x += x >> 16
   166  	x += x >> 32
   167  	return int(x) & (1<<7 - 1)
   168  }
   169  
   170  // --- RotateLeft ---
   171  
   172  // RotateLeft returns the value of x rotated left by (k mod [UintSize]) bits.
   173  // To rotate x right by k bits, call RotateLeft(x, -k).
   174  //
   175  // This function's execution time does not depend on the inputs.
   176  func RotateLeft(x uint, k int) uint {
   177  	if UintSize == 32 {
   178  		return uint(RotateLeft32(uint32(x), k))
   179  	}
   180  	return uint(RotateLeft64(uint64(x), k))
   181  }
   182  
   183  // RotateLeft8 returns the value of x rotated left by (k mod 8) bits.
   184  // To rotate x right by k bits, call RotateLeft8(x, -k).
   185  //
   186  // This function's execution time does not depend on the inputs.
   187  func RotateLeft8(x uint8, k int) uint8 {
   188  	const n = 8
   189  	s := uint(k) & (n - 1)
   190  	return x<<s | x>>(n-s)
   191  }
   192  
   193  // RotateLeft16 returns the value of x rotated left by (k mod 16) bits.
   194  // To rotate x right by k bits, call RotateLeft16(x, -k).
   195  //
   196  // This function's execution time does not depend on the inputs.
   197  func RotateLeft16(x uint16, k int) uint16 {
   198  	const n = 16
   199  	s := uint(k) & (n - 1)
   200  	return x<<s | x>>(n-s)
   201  }
   202  
   203  // RotateLeft32 returns the value of x rotated left by (k mod 32) bits.
   204  // To rotate x right by k bits, call RotateLeft32(x, -k).
   205  //
   206  // This function's execution time does not depend on the inputs.
   207  func RotateLeft32(x uint32, k int) uint32 {
   208  	const n = 32
   209  	s := uint(k) & (n - 1)
   210  	return x<<s | x>>(n-s)
   211  }
   212  
   213  // RotateLeft64 returns the value of x rotated left by (k mod 64) bits.
   214  // To rotate x right by k bits, call RotateLeft64(x, -k).
   215  //
   216  // This function's execution time does not depend on the inputs.
   217  func RotateLeft64(x uint64, k int) uint64 {
   218  	const n = 64
   219  	s := uint(k) & (n - 1)
   220  	return x<<s | x>>(n-s)
   221  }
   222  
   223  // --- Reverse ---
   224  
   225  // Reverse returns the value of x with its bits in reversed order.
   226  func Reverse(x uint) uint {
   227  	if UintSize == 32 {
   228  		return uint(Reverse32(uint32(x)))
   229  	}
   230  	return uint(Reverse64(uint64(x)))
   231  }
   232  
   233  // Reverse8 returns the value of x with its bits in reversed order.
   234  func Reverse8(x uint8) uint8 {
   235  	return rev8tab[x]
   236  }
   237  
   238  // Reverse16 returns the value of x with its bits in reversed order.
   239  func Reverse16(x uint16) uint16 {
   240  	return uint16(rev8tab[x>>8]) | uint16(rev8tab[x&0xff])<<8
   241  }
   242  
   243  // Reverse32 returns the value of x with its bits in reversed order.
   244  func Reverse32(x uint32) uint32 {
   245  	const m = 1<<32 - 1
   246  	x = x>>1&(m0&m) | x&(m0&m)<<1
   247  	x = x>>2&(m1&m) | x&(m1&m)<<2
   248  	x = x>>4&(m2&m) | x&(m2&m)<<4
   249  	return ReverseBytes32(x)
   250  }
   251  
   252  // Reverse64 returns the value of x with its bits in reversed order.
   253  func Reverse64(x uint64) uint64 {
   254  	const m = 1<<64 - 1
   255  	x = x>>1&(m0&m) | x&(m0&m)<<1
   256  	x = x>>2&(m1&m) | x&(m1&m)<<2
   257  	x = x>>4&(m2&m) | x&(m2&m)<<4
   258  	return ReverseBytes64(x)
   259  }
   260  
   261  // --- ReverseBytes ---
   262  
   263  // ReverseBytes returns the value of x with its bytes in reversed order.
   264  //
   265  // This function's execution time does not depend on the inputs.
   266  func ReverseBytes(x uint) uint {
   267  	if UintSize == 32 {
   268  		return uint(ReverseBytes32(uint32(x)))
   269  	}
   270  	return uint(ReverseBytes64(uint64(x)))
   271  }
   272  
   273  // ReverseBytes16 returns the value of x with its bytes in reversed order.
   274  //
   275  // This function's execution time does not depend on the inputs.
   276  func ReverseBytes16(x uint16) uint16 {
   277  	return x>>8 | x<<8
   278  }
   279  
   280  // ReverseBytes32 returns the value of x with its bytes in reversed order.
   281  //
   282  // This function's execution time does not depend on the inputs.
   283  func ReverseBytes32(x uint32) uint32 {
   284  	const m = 1<<32 - 1
   285  	x = x>>8&(m3&m) | x&(m3&m)<<8
   286  	return x>>16 | x<<16
   287  }
   288  
   289  // ReverseBytes64 returns the value of x with its bytes in reversed order.
   290  //
   291  // This function's execution time does not depend on the inputs.
   292  func ReverseBytes64(x uint64) uint64 {
   293  	const m = 1<<64 - 1
   294  	x = x>>8&(m3&m) | x&(m3&m)<<8
   295  	x = x>>16&(m4&m) | x&(m4&m)<<16
   296  	return x>>32 | x<<32
   297  }
   298  
   299  // --- Len ---
   300  
   301  // Len returns the minimum number of bits required to represent x; the result is 0 for x == 0.
   302  func Len(x uint) int {
   303  	if UintSize == 32 {
   304  		return Len32(uint32(x))
   305  	}
   306  	return Len64(uint64(x))
   307  }
   308  
   309  // Len8 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
   310  func Len8(x uint8) int {
   311  	return int(len8tab[x])
   312  }
   313  
   314  // Len16 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
   315  func Len16(x uint16) (n int) {
   316  	if x >= 1<<8 {
   317  		x >>= 8
   318  		n = 8
   319  	}
   320  	return n + int(len8tab[x])
   321  }
   322  
   323  // Len32 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
   324  func Len32(x uint32) (n int) {
   325  	if x >= 1<<16 {
   326  		x >>= 16
   327  		n = 16
   328  	}
   329  	if x >= 1<<8 {
   330  		x >>= 8
   331  		n += 8
   332  	}
   333  	return n + int(len8tab[x])
   334  }
   335  
   336  // Len64 returns the minimum number of bits required to represent x; the result is 0 for x == 0.
   337  func Len64(x uint64) (n int) {
   338  	if x >= 1<<32 {
   339  		x >>= 32
   340  		n = 32
   341  	}
   342  	if x >= 1<<16 {
   343  		x >>= 16
   344  		n += 16
   345  	}
   346  	if x >= 1<<8 {
   347  		x >>= 8
   348  		n += 8
   349  	}
   350  	return n + int(len8tab[x])
   351  }
   352  
   353  // --- Add with carry ---
   354  
   355  // Add returns the sum with carry of x, y and carry: sum = x + y + carry.
   356  // The carry input must be 0 or 1; otherwise the behavior is undefined.
   357  // The carryOut output is guaranteed to be 0 or 1.
   358  //
   359  // This function's execution time does not depend on the inputs.
   360  func Add(x, y, carry uint) (sum, carryOut uint) {
   361  	if UintSize == 32 {
   362  		s32, c32 := Add32(uint32(x), uint32(y), uint32(carry))
   363  		return uint(s32), uint(c32)
   364  	}
   365  	s64, c64 := Add64(uint64(x), uint64(y), uint64(carry))
   366  	return uint(s64), uint(c64)
   367  }
   368  
   369  // Add32 returns the sum with carry of x, y and carry: sum = x + y + carry.
   370  // The carry input must be 0 or 1; otherwise the behavior is undefined.
   371  // The carryOut output is guaranteed to be 0 or 1.
   372  //
   373  // This function's execution time does not depend on the inputs.
   374  func Add32(x, y, carry uint32) (sum, carryOut uint32) {
   375  	sum64 := uint64(x) + uint64(y) + uint64(carry)
   376  	sum = uint32(sum64)
   377  	carryOut = uint32(sum64 >> 32)
   378  	return
   379  }
   380  
   381  // Add64 returns the sum with carry of x, y and carry: sum = x + y + carry.
   382  // The carry input must be 0 or 1; otherwise the behavior is undefined.
   383  // The carryOut output is guaranteed to be 0 or 1.
   384  //
   385  // This function's execution time does not depend on the inputs.
   386  func Add64(x, y, carry uint64) (sum, carryOut uint64) {
   387  	sum = x + y + carry
   388  	// The sum will overflow if both top bits are set (x & y) or if one of them
   389  	// is (x | y), and a carry from the lower place happened. If such a carry
   390  	// happens, the top bit will be 1 + 0 + 1 = 0 (&^ sum).
   391  	carryOut = ((x & y) | ((x | y) &^ sum)) >> 63
   392  	return
   393  }
   394  
   395  // --- Subtract with borrow ---
   396  
   397  // Sub returns the difference of x, y and borrow: diff = x - y - borrow.
   398  // The borrow input must be 0 or 1; otherwise the behavior is undefined.
   399  // The borrowOut output is guaranteed to be 0 or 1.
   400  //
   401  // This function's execution time does not depend on the inputs.
   402  func Sub(x, y, borrow uint) (diff, borrowOut uint) {
   403  	if UintSize == 32 {
   404  		d32, b32 := Sub32(uint32(x), uint32(y), uint32(borrow))
   405  		return uint(d32), uint(b32)
   406  	}
   407  	d64, b64 := Sub64(uint64(x), uint64(y), uint64(borrow))
   408  	return uint(d64), uint(b64)
   409  }
   410  
   411  // Sub32 returns the difference of x, y and borrow, diff = x - y - borrow.
   412  // The borrow input must be 0 or 1; otherwise the behavior is undefined.
   413  // The borrowOut output is guaranteed to be 0 or 1.
   414  //
   415  // This function's execution time does not depend on the inputs.
   416  func Sub32(x, y, borrow uint32) (diff, borrowOut uint32) {
   417  	diff = x - y - borrow
   418  	// The difference will underflow if the top bit of x is not set and the top
   419  	// bit of y is set (^x & y) or if they are the same (^(x ^ y)) and a borrow
   420  	// from the lower place happens. If that borrow happens, the result will be
   421  	// 1 - 1 - 1 = 0 - 0 - 1 = 1 (& diff).
   422  	borrowOut = ((^x & y) | (^(x ^ y) & diff)) >> 31
   423  	return
   424  }
   425  
   426  // Sub64 returns the difference of x, y and borrow: diff = x - y - borrow.
   427  // The borrow input must be 0 or 1; otherwise the behavior is undefined.
   428  // The borrowOut output is guaranteed to be 0 or 1.
   429  //
   430  // This function's execution time does not depend on the inputs.
   431  func Sub64(x, y, borrow uint64) (diff, borrowOut uint64) {
   432  	diff = x - y - borrow
   433  	// See Sub32 for the bit logic.
   434  	borrowOut = ((^x & y) | (^(x ^ y) & diff)) >> 63
   435  	return
   436  }
   437  
   438  // --- Full-width multiply ---
   439  
   440  // Mul returns the full-width product of x and y: (hi, lo) = x * y
   441  // with the product bits' upper half returned in hi and the lower
   442  // half returned in lo.
   443  //
   444  // This function's execution time does not depend on the inputs.
   445  func Mul(x, y uint) (hi, lo uint) {
   446  	if UintSize == 32 {
   447  		h, l := Mul32(uint32(x), uint32(y))
   448  		return uint(h), uint(l)
   449  	}
   450  	h, l := Mul64(uint64(x), uint64(y))
   451  	return uint(h), uint(l)
   452  }
   453  
   454  // Mul32 returns the 64-bit product of x and y: (hi, lo) = x * y
   455  // with the product bits' upper half returned in hi and the lower
   456  // half returned in lo.
   457  //
   458  // This function's execution time does not depend on the inputs.
   459  func Mul32(x, y uint32) (hi, lo uint32) {
   460  	tmp := uint64(x) * uint64(y)
   461  	hi, lo = uint32(tmp>>32), uint32(tmp)
   462  	return
   463  }
   464  
   465  // Mul64 returns the 128-bit product of x and y: (hi, lo) = x * y
   466  // with the product bits' upper half returned in hi and the lower
   467  // half returned in lo.
   468  //
   469  // This function's execution time does not depend on the inputs.
   470  func Mul64(x, y uint64) (hi, lo uint64) {
   471  	const mask32 = 1<<32 - 1
   472  	x0 := x & mask32
   473  	x1 := x >> 32
   474  	y0 := y & mask32
   475  	y1 := y >> 32
   476  	w0 := x0 * y0
   477  	t := x1*y0 + w0>>32
   478  	w1 := t & mask32
   479  	w2 := t >> 32
   480  	w1 += x0 * y1
   481  	hi = x1*y1 + w2 + w1>>32
   482  	lo = x * y
   483  	return
   484  }
   485  
   486  // --- Full-width divide ---
   487  
   488  // Div returns the quotient and remainder of (hi, lo) divided by y:
   489  // quo = (hi, lo)/y, rem = (hi, lo)%y with the dividend bits' upper
   490  // half in parameter hi and the lower half in parameter lo.
   491  // Div panics for y == 0 (division by zero) or y <= hi (quotient overflow).
   492  func Div(hi, lo, y uint) (quo, rem uint) {
   493  	if UintSize == 32 {
   494  		q, r := Div32(uint32(hi), uint32(lo), uint32(y))
   495  		return uint(q), uint(r)
   496  	}
   497  	q, r := Div64(uint64(hi), uint64(lo), uint64(y))
   498  	return uint(q), uint(r)
   499  }
   500  
   501  // Div32 returns the quotient and remainder of (hi, lo) divided by y:
   502  // quo = (hi, lo)/y, rem = (hi, lo)%y with the dividend bits' upper
   503  // half in parameter hi and the lower half in parameter lo.
   504  // Div32 panics for y == 0 (division by zero) or y <= hi (quotient overflow).
   505  func Div32(hi, lo, y uint32) (quo, rem uint32) {
   506  	if y != 0 && y <= hi {
   507  		panic(overflowError)
   508  	}
   509  	z := uint64(hi)<<32 | uint64(lo)
   510  	quo, rem = uint32(z/uint64(y)), uint32(z%uint64(y))
   511  	return
   512  }
   513  
   514  // Div64 returns the quotient and remainder of (hi, lo) divided by y:
   515  // quo = (hi, lo)/y, rem = (hi, lo)%y with the dividend bits' upper
   516  // half in parameter hi and the lower half in parameter lo.
   517  // Div64 panics for y == 0 (division by zero) or y <= hi (quotient overflow).
   518  func Div64(hi, lo, y uint64) (quo, rem uint64) {
   519  	if y == 0 {
   520  		panic(divideError)
   521  	}
   522  	if y <= hi {
   523  		panic(overflowError)
   524  	}
   525  
   526  	// If high part is zero, we can directly return the results.
   527  	if hi == 0 {
   528  		return lo / y, lo % y
   529  	}
   530  
   531  	s := uint(LeadingZeros64(y))
   532  	y <<= s
   533  
   534  	const (
   535  		two32  = 1 << 32
   536  		mask32 = two32 - 1
   537  	)
   538  	yn1 := y >> 32
   539  	yn0 := y & mask32
   540  	un32 := hi<<s | lo>>(64-s)
   541  	un10 := lo << s
   542  	un1 := un10 >> 32
   543  	un0 := un10 & mask32
   544  	q1 := un32 / yn1
   545  	rhat := un32 - q1*yn1
   546  
   547  	for q1 >= two32 || q1*yn0 > two32*rhat+un1 {
   548  		q1--
   549  		rhat += yn1
   550  		if rhat >= two32 {
   551  			break
   552  		}
   553  	}
   554  
   555  	un21 := un32*two32 + un1 - q1*y
   556  	q0 := un21 / yn1
   557  	rhat = un21 - q0*yn1
   558  
   559  	for q0 >= two32 || q0*yn0 > two32*rhat+un0 {
   560  		q0--
   561  		rhat += yn1
   562  		if rhat >= two32 {
   563  			break
   564  		}
   565  	}
   566  
   567  	return q1*two32 + q0, (un21*two32 + un0 - q0*y) >> s
   568  }
   569  
   570  // Rem returns the remainder of (hi, lo) divided by y. Rem panics for
   571  // y == 0 (division by zero) but, unlike Div, it doesn't panic on a
   572  // quotient overflow.
   573  func Rem(hi, lo, y uint) uint {
   574  	if UintSize == 32 {
   575  		return uint(Rem32(uint32(hi), uint32(lo), uint32(y)))
   576  	}
   577  	return uint(Rem64(uint64(hi), uint64(lo), uint64(y)))
   578  }
   579  
   580  // Rem32 returns the remainder of (hi, lo) divided by y. Rem32 panics
   581  // for y == 0 (division by zero) but, unlike [Div32], it doesn't panic
   582  // on a quotient overflow.
   583  func Rem32(hi, lo, y uint32) uint32 {
   584  	return uint32((uint64(hi)<<32 | uint64(lo)) % uint64(y))
   585  }
   586  
   587  // Rem64 returns the remainder of (hi, lo) divided by y. Rem64 panics
   588  // for y == 0 (division by zero) but, unlike [Div64], it doesn't panic
   589  // on a quotient overflow.
   590  func Rem64(hi, lo, y uint64) uint64 {
   591  	// We scale down hi so that hi < y, then use Div64 to compute the
   592  	// rem with the guarantee that it won't panic on quotient overflow.
   593  	// Given that
   594  	//   hi ≡ hi%y    (mod y)
   595  	// we have
   596  	//   hi<<64 + lo ≡ (hi%y)<<64 + lo    (mod y)
   597  	_, rem := Div64(hi%y, lo, y)
   598  	return rem
   599  }
   600  

View as plain text