diff options
| author | 2024-03-04 09:42:11 +0000 | |
|---|---|---|
| committer | 2024-03-04 09:42:11 +0000 | |
| commit | adb4cdcf6c9eacd369eaaf5b21774b198d57c040 (patch) | |
| tree | a4f9c8fe2ce147fa952bcb795690afb9bb2affcb /vendor/lukechampine.com | |
| parent | [bugfix] update postgresqlstmt to correctly use postgres err hook (#2711) (diff) | |
| download | gotosocial-adb4cdcf6c9eacd369eaaf5b21774b198d57c040.tar.xz | |
[chore]: Bump modernc.org/sqlite from 1.28.0 to 1.29.2 (#2718)
Diffstat (limited to 'vendor/lukechampine.com')
| -rw-r--r-- | vendor/lukechampine.com/uint128/LICENSE | 21 | ||||
| -rw-r--r-- | vendor/lukechampine.com/uint128/README.md | 46 | ||||
| -rw-r--r-- | vendor/lukechampine.com/uint128/uint128.go | 440 |
3 files changed, 0 insertions, 507 deletions
diff --git a/vendor/lukechampine.com/uint128/LICENSE b/vendor/lukechampine.com/uint128/LICENSE deleted file mode 100644 index a14c6cf2a..000000000 --- a/vendor/lukechampine.com/uint128/LICENSE +++ /dev/null @@ -1,21 +0,0 @@ -The MIT License (MIT) - -Copyright (c) 2019 Luke Champine - -Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in -all copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN -THE SOFTWARE. diff --git a/vendor/lukechampine.com/uint128/README.md b/vendor/lukechampine.com/uint128/README.md deleted file mode 100644 index 1ea5d7df1..000000000 --- a/vendor/lukechampine.com/uint128/README.md +++ /dev/null @@ -1,46 +0,0 @@ -uint128 -------- - -[](https://godoc.org/github.com/lukechampine/uint128) -[](https://goreportcard.com/report/github.com/lukechampine/uint128) - -``` -go get lukechampine.com/uint128 -``` - -`uint128` provides a high-performance `Uint128` type that supports standard arithmetic -operations. Unlike `math/big`, operations on `Uint128` values always produce new values -instead of modifying a pointer receiver. A `Uint128` value is therefore immutable, just -like `uint64` and friends. - -The name `uint128.Uint128` stutters, so I recommend either using a "dot import" -or aliasing `uint128.Uint128` to give it a project-specific name. Embedding the type -is not recommended, because methods will still return `uint128.Uint128`; this means that, -if you want to extend the type with new methods, your best bet is probably to copy the -source code wholesale and rename the identifier. ¯\\\_(ツ)\_/¯ - - -# Benchmarks - -Addition, multiplication, and subtraction are on par with their native 64-bit -equivalents. Division is slower: ~20x slower when dividing a `Uint128` by a -`uint64`, and ~100x slower when dividing by a `Uint128`. However, division is -still faster than with `big.Int` (for the same operands), especially when -dividing by a `uint64`. - -``` -BenchmarkArithmetic/Add-4 2000000000 0.45 ns/op 0 B/op 0 allocs/op -BenchmarkArithmetic/Sub-4 2000000000 0.67 ns/op 0 B/op 0 allocs/op -BenchmarkArithmetic/Mul-4 2000000000 0.42 ns/op 0 B/op 0 allocs/op -BenchmarkArithmetic/Lsh-4 2000000000 1.06 ns/op 0 B/op 0 allocs/op -BenchmarkArithmetic/Rsh-4 2000000000 1.06 ns/op 0 B/op 0 allocs/op - -BenchmarkDivision/native_64/64-4 2000000000 0.39 ns/op 0 B/op 0 allocs/op -BenchmarkDivision/Div_128/64-4 2000000000 6.28 ns/op 0 B/op 0 allocs/op -BenchmarkDivision/Div_128/128-4 30000000 45.2 ns/op 0 B/op 0 allocs/op -BenchmarkDivision/big.Int_128/64-4 20000000 98.2 ns/op 8 B/op 1 allocs/op -BenchmarkDivision/big.Int_128/128-4 30000000 53.4 ns/op 48 B/op 1 allocs/op - -BenchmarkString/Uint128-4 10000000 173 ns/op 48 B/op 1 allocs/op -BenchmarkString/big.Int-4 5000000 350 ns/op 144 B/op 3 allocs/op -``` diff --git a/vendor/lukechampine.com/uint128/uint128.go b/vendor/lukechampine.com/uint128/uint128.go deleted file mode 100644 index 04e65783a..000000000 --- a/vendor/lukechampine.com/uint128/uint128.go +++ /dev/null @@ -1,440 +0,0 @@ -package uint128 // import "lukechampine.com/uint128" - -import ( - "encoding/binary" - "errors" - "fmt" - "math" - "math/big" - "math/bits" -) - -// Zero is a zero-valued uint128. -var Zero Uint128 - -// Max is the largest possible uint128 value. -var Max = New(math.MaxUint64, math.MaxUint64) - -// A Uint128 is an unsigned 128-bit number. -type Uint128 struct { - Lo, Hi uint64 -} - -// IsZero returns true if u == 0. -func (u Uint128) IsZero() bool { - // NOTE: we do not compare against Zero, because that is a global variable - // that could be modified. - return u == Uint128{} -} - -// Equals returns true if u == v. -// -// Uint128 values can be compared directly with ==, but use of the Equals method -// is preferred for consistency. -func (u Uint128) Equals(v Uint128) bool { - return u == v -} - -// Equals64 returns true if u == v. -func (u Uint128) Equals64(v uint64) bool { - return u.Lo == v && u.Hi == 0 -} - -// Cmp compares u and v and returns: -// -// -1 if u < v -// 0 if u == v -// +1 if u > v -// -func (u Uint128) Cmp(v Uint128) int { - if u == v { - return 0 - } else if u.Hi < v.Hi || (u.Hi == v.Hi && u.Lo < v.Lo) { - return -1 - } else { - return 1 - } -} - -// Cmp64 compares u and v and returns: -// -// -1 if u < v -// 0 if u == v -// +1 if u > v -// -func (u Uint128) Cmp64(v uint64) int { - if u.Hi == 0 && u.Lo == v { - return 0 - } else if u.Hi == 0 && u.Lo < v { - return -1 - } else { - return 1 - } -} - -// And returns u&v. -func (u Uint128) And(v Uint128) Uint128 { - return Uint128{u.Lo & v.Lo, u.Hi & v.Hi} -} - -// And64 returns u&v. -func (u Uint128) And64(v uint64) Uint128 { - return Uint128{u.Lo & v, u.Hi & 0} -} - -// Or returns u|v. -func (u Uint128) Or(v Uint128) Uint128 { - return Uint128{u.Lo | v.Lo, u.Hi | v.Hi} -} - -// Or64 returns u|v. -func (u Uint128) Or64(v uint64) Uint128 { - return Uint128{u.Lo | v, u.Hi | 0} -} - -// Xor returns u^v. -func (u Uint128) Xor(v Uint128) Uint128 { - return Uint128{u.Lo ^ v.Lo, u.Hi ^ v.Hi} -} - -// Xor64 returns u^v. -func (u Uint128) Xor64(v uint64) Uint128 { - return Uint128{u.Lo ^ v, u.Hi ^ 0} -} - -// Add returns u+v. -func (u Uint128) Add(v Uint128) Uint128 { - lo, carry := bits.Add64(u.Lo, v.Lo, 0) - hi, carry := bits.Add64(u.Hi, v.Hi, carry) - if carry != 0 { - panic("overflow") - } - return Uint128{lo, hi} -} - -// AddWrap returns u+v with wraparound semantics; for example, -// Max.AddWrap(From64(1)) == Zero. -func (u Uint128) AddWrap(v Uint128) Uint128 { - lo, carry := bits.Add64(u.Lo, v.Lo, 0) - hi, _ := bits.Add64(u.Hi, v.Hi, carry) - return Uint128{lo, hi} -} - -// Add64 returns u+v. -func (u Uint128) Add64(v uint64) Uint128 { - lo, carry := bits.Add64(u.Lo, v, 0) - hi, carry := bits.Add64(u.Hi, 0, carry) - if carry != 0 { - panic("overflow") - } - return Uint128{lo, hi} -} - -// AddWrap64 returns u+v with wraparound semantics; for example, -// Max.AddWrap64(1) == Zero. -func (u Uint128) AddWrap64(v uint64) Uint128 { - lo, carry := bits.Add64(u.Lo, v, 0) - hi := u.Hi + carry - return Uint128{lo, hi} -} - -// Sub returns u-v. -func (u Uint128) Sub(v Uint128) Uint128 { - lo, borrow := bits.Sub64(u.Lo, v.Lo, 0) - hi, borrow := bits.Sub64(u.Hi, v.Hi, borrow) - if borrow != 0 { - panic("underflow") - } - return Uint128{lo, hi} -} - -// SubWrap returns u-v with wraparound semantics; for example, -// Zero.SubWrap(From64(1)) == Max. -func (u Uint128) SubWrap(v Uint128) Uint128 { - lo, borrow := bits.Sub64(u.Lo, v.Lo, 0) - hi, _ := bits.Sub64(u.Hi, v.Hi, borrow) - return Uint128{lo, hi} -} - -// Sub64 returns u-v. -func (u Uint128) Sub64(v uint64) Uint128 { - lo, borrow := bits.Sub64(u.Lo, v, 0) - hi, borrow := bits.Sub64(u.Hi, 0, borrow) - if borrow != 0 { - panic("underflow") - } - return Uint128{lo, hi} -} - -// SubWrap64 returns u-v with wraparound semantics; for example, -// Zero.SubWrap64(1) == Max. -func (u Uint128) SubWrap64(v uint64) Uint128 { - lo, borrow := bits.Sub64(u.Lo, v, 0) - hi := u.Hi - borrow - return Uint128{lo, hi} -} - -// Mul returns u*v, panicking on overflow. -func (u Uint128) Mul(v Uint128) Uint128 { - hi, lo := bits.Mul64(u.Lo, v.Lo) - p0, p1 := bits.Mul64(u.Hi, v.Lo) - p2, p3 := bits.Mul64(u.Lo, v.Hi) - hi, c0 := bits.Add64(hi, p1, 0) - hi, c1 := bits.Add64(hi, p3, c0) - if (u.Hi != 0 && v.Hi != 0) || p0 != 0 || p2 != 0 || c1 != 0 { - panic("overflow") - } - return Uint128{lo, hi} -} - -// MulWrap returns u*v with wraparound semantics; for example, -// Max.MulWrap(Max) == 1. -func (u Uint128) MulWrap(v Uint128) Uint128 { - hi, lo := bits.Mul64(u.Lo, v.Lo) - hi += u.Hi*v.Lo + u.Lo*v.Hi - return Uint128{lo, hi} -} - -// Mul64 returns u*v, panicking on overflow. -func (u Uint128) Mul64(v uint64) Uint128 { - hi, lo := bits.Mul64(u.Lo, v) - p0, p1 := bits.Mul64(u.Hi, v) - hi, c0 := bits.Add64(hi, p1, 0) - if p0 != 0 || c0 != 0 { - panic("overflow") - } - return Uint128{lo, hi} -} - -// MulWrap64 returns u*v with wraparound semantics; for example, -// Max.MulWrap64(2) == Max.Sub64(1). -func (u Uint128) MulWrap64(v uint64) Uint128 { - hi, lo := bits.Mul64(u.Lo, v) - hi += u.Hi * v - return Uint128{lo, hi} -} - -// Div returns u/v. -func (u Uint128) Div(v Uint128) Uint128 { - q, _ := u.QuoRem(v) - return q -} - -// Div64 returns u/v. -func (u Uint128) Div64(v uint64) Uint128 { - q, _ := u.QuoRem64(v) - return q -} - -// QuoRem returns q = u/v and r = u%v. -func (u Uint128) QuoRem(v Uint128) (q, r Uint128) { - if v.Hi == 0 { - var r64 uint64 - q, r64 = u.QuoRem64(v.Lo) - r = From64(r64) - } else { - // generate a "trial quotient," guaranteed to be within 1 of the actual - // quotient, then adjust. - n := uint(bits.LeadingZeros64(v.Hi)) - v1 := v.Lsh(n) - u1 := u.Rsh(1) - tq, _ := bits.Div64(u1.Hi, u1.Lo, v1.Hi) - tq >>= 63 - n - if tq != 0 { - tq-- - } - q = From64(tq) - // calculate remainder using trial quotient, then adjust if remainder is - // greater than divisor - r = u.Sub(v.Mul64(tq)) - if r.Cmp(v) >= 0 { - q = q.Add64(1) - r = r.Sub(v) - } - } - return -} - -// QuoRem64 returns q = u/v and r = u%v. -func (u Uint128) QuoRem64(v uint64) (q Uint128, r uint64) { - if u.Hi < v { - q.Lo, r = bits.Div64(u.Hi, u.Lo, v) - } else { - q.Hi, r = bits.Div64(0, u.Hi, v) - q.Lo, r = bits.Div64(r, u.Lo, v) - } - return -} - -// Mod returns r = u%v. -func (u Uint128) Mod(v Uint128) (r Uint128) { - _, r = u.QuoRem(v) - return -} - -// Mod64 returns r = u%v. -func (u Uint128) Mod64(v uint64) (r uint64) { - _, r = u.QuoRem64(v) - return -} - -// Lsh returns u<<n. -func (u Uint128) Lsh(n uint) (s Uint128) { - if n > 64 { - s.Lo = 0 - s.Hi = u.Lo << (n - 64) - } else { - s.Lo = u.Lo << n - s.Hi = u.Hi<<n | u.Lo>>(64-n) - } - return -} - -// Rsh returns u>>n. -func (u Uint128) Rsh(n uint) (s Uint128) { - if n > 64 { - s.Lo = u.Hi >> (n - 64) - s.Hi = 0 - } else { - s.Lo = u.Lo>>n | u.Hi<<(64-n) - s.Hi = u.Hi >> n - } - return -} - -// LeadingZeros returns the number of leading zero bits in u; the result is 128 -// for u == 0. -func (u Uint128) LeadingZeros() int { - if u.Hi > 0 { - return bits.LeadingZeros64(u.Hi) - } - return 64 + bits.LeadingZeros64(u.Lo) -} - -// TrailingZeros returns the number of trailing zero bits in u; the result is -// 128 for u == 0. -func (u Uint128) TrailingZeros() int { - if u.Lo > 0 { - return bits.TrailingZeros64(u.Lo) - } - return 64 + bits.TrailingZeros64(u.Hi) -} - -// OnesCount returns the number of one bits ("population count") in u. -func (u Uint128) OnesCount() int { - return bits.OnesCount64(u.Hi) + bits.OnesCount64(u.Lo) -} - -// RotateLeft returns the value of u rotated left by (k mod 128) bits. -func (u Uint128) RotateLeft(k int) Uint128 { - const n = 128 - s := uint(k) & (n - 1) - return u.Lsh(s).Or(u.Rsh(n - s)) -} - -// RotateRight returns the value of u rotated left by (k mod 128) bits. -func (u Uint128) RotateRight(k int) Uint128 { - return u.RotateLeft(-k) -} - -// Reverse returns the value of u with its bits in reversed order. -func (u Uint128) Reverse() Uint128 { - return Uint128{bits.Reverse64(u.Hi), bits.Reverse64(u.Lo)} -} - -// ReverseBytes returns the value of u with its bytes in reversed order. -func (u Uint128) ReverseBytes() Uint128 { - return Uint128{bits.ReverseBytes64(u.Hi), bits.ReverseBytes64(u.Lo)} -} - -// Len returns the minimum number of bits required to represent u; the result is -// 0 for u == 0. -func (u Uint128) Len() int { - return 128 - u.LeadingZeros() -} - -// String returns the base-10 representation of u as a string. -func (u Uint128) String() string { - if u.IsZero() { - return "0" - } - buf := []byte("0000000000000000000000000000000000000000") // log10(2^128) < 40 - for i := len(buf); ; i -= 19 { - q, r := u.QuoRem64(1e19) // largest power of 10 that fits in a uint64 - var n int - for ; r != 0; r /= 10 { - n++ - buf[i-n] += byte(r % 10) - } - if q.IsZero() { - return string(buf[i-n:]) - } - u = q - } -} - -// PutBytes stores u in b in little-endian order. It panics if len(b) < 16. -func (u Uint128) PutBytes(b []byte) { - binary.LittleEndian.PutUint64(b[:8], u.Lo) - binary.LittleEndian.PutUint64(b[8:], u.Hi) -} - -// Big returns u as a *big.Int. -func (u Uint128) Big() *big.Int { - i := new(big.Int).SetUint64(u.Hi) - i = i.Lsh(i, 64) - i = i.Xor(i, new(big.Int).SetUint64(u.Lo)) - return i -} - -// Scan implements fmt.Scanner. -func (u *Uint128) Scan(s fmt.ScanState, ch rune) error { - i := new(big.Int) - if err := i.Scan(s, ch); err != nil { - return err - } else if i.Sign() < 0 { - return errors.New("value cannot be negative") - } else if i.BitLen() > 128 { - return errors.New("value overflows Uint128") - } - u.Lo = i.Uint64() - u.Hi = i.Rsh(i, 64).Uint64() - return nil -} - -// New returns the Uint128 value (lo,hi). -func New(lo, hi uint64) Uint128 { - return Uint128{lo, hi} -} - -// From64 converts v to a Uint128 value. -func From64(v uint64) Uint128 { - return New(v, 0) -} - -// FromBytes converts b to a Uint128 value. -func FromBytes(b []byte) Uint128 { - return New( - binary.LittleEndian.Uint64(b[:8]), - binary.LittleEndian.Uint64(b[8:]), - ) -} - -// FromBig converts i to a Uint128 value. It panics if i is negative or -// overflows 128 bits. -func FromBig(i *big.Int) (u Uint128) { - if i.Sign() < 0 { - panic("value cannot be negative") - } else if i.BitLen() > 128 { - panic("value overflows Uint128") - } - u.Lo = i.Uint64() - u.Hi = i.Rsh(i, 64).Uint64() - return u -} - -// FromString parses s as a Uint128 value. -func FromString(s string) (u Uint128, err error) { - _, err = fmt.Sscan(s, &u) - return -} |
