1// Copyright 2016 The Oklog Authors 2// Licensed under the Apache License, Version 2.0 (the "License"); 3// you may not use this file except in compliance with the License. 4// You may obtain a copy of the License at 5// 6// http://www.apache.org/licenses/LICENSE-2.0 7// 8// Unless required by applicable law or agreed to in writing, software 9// distributed under the License is distributed on an "AS IS" BASIS, 10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11// See the License for the specific language governing permissions and 12// limitations under the License. 13 14package ulid 15 16import ( 17 "bufio" 18 "bytes" 19 "database/sql/driver" 20 "encoding/binary" 21 "errors" 22 "io" 23 "math" 24 "math/bits" 25 "math/rand" 26 "time" 27) 28 29/* 30An ULID is a 16 byte Universally Unique Lexicographically Sortable Identifier 31 32 The components are encoded as 16 octets. 33 Each component is encoded with the MSB first (network byte order). 34 35 0 1 2 3 36 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 37 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 38 | 32_bit_uint_time_high | 39 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 40 | 16_bit_uint_time_low | 16_bit_uint_random | 41 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 42 | 32_bit_uint_random | 43 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 44 | 32_bit_uint_random | 45 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 46*/ 47type ULID [16]byte 48 49var ( 50 // ErrDataSize is returned when parsing or unmarshaling ULIDs with the wrong 51 // data size. 52 ErrDataSize = errors.New("ulid: bad data size when unmarshaling") 53 54 // ErrInvalidCharacters is returned when parsing or unmarshaling ULIDs with 55 // invalid Base32 encodings. 56 ErrInvalidCharacters = errors.New("ulid: bad data characters when unmarshaling") 57 58 // ErrBufferSize is returned when marshalling ULIDs to a buffer of insufficient 59 // size. 60 ErrBufferSize = errors.New("ulid: bad buffer size when marshaling") 61 62 // ErrBigTime is returned when constructing an ULID with a time that is larger 63 // than MaxTime. 64 ErrBigTime = errors.New("ulid: time too big") 65 66 // ErrOverflow is returned when unmarshaling a ULID whose first character is 67 // larger than 7, thereby exceeding the valid bit depth of 128. 68 ErrOverflow = errors.New("ulid: overflow when unmarshaling") 69 70 // ErrMonotonicOverflow is returned by a Monotonic entropy source when 71 // incrementing the previous ULID's entropy bytes would result in overflow. 72 ErrMonotonicOverflow = errors.New("ulid: monotonic entropy overflow") 73 74 // ErrScanValue is returned when the value passed to scan cannot be unmarshaled 75 // into the ULID. 76 ErrScanValue = errors.New("ulid: source value must be a string or byte slice") 77) 78 79// New returns an ULID with the given Unix milliseconds timestamp and an 80// optional entropy source. Use the Timestamp function to convert 81// a time.Time to Unix milliseconds. 82// 83// ErrBigTime is returned when passing a timestamp bigger than MaxTime. 84// Reading from the entropy source may also return an error. 85func New(ms uint64, entropy io.Reader) (id ULID, err error) { 86 if err = id.SetTime(ms); err != nil { 87 return id, err 88 } 89 90 switch e := entropy.(type) { 91 case nil: 92 return id, err 93 case *monotonic: 94 err = e.MonotonicRead(ms, id[6:]) 95 default: 96 _, err = io.ReadFull(e, id[6:]) 97 } 98 99 return id, err 100} 101 102// MustNew is a convenience function equivalent to New that panics on failure 103// instead of returning an error. 104func MustNew(ms uint64, entropy io.Reader) ULID { 105 id, err := New(ms, entropy) 106 if err != nil { 107 panic(err) 108 } 109 return id 110} 111 112// Parse parses an encoded ULID, returning an error in case of failure. 113// 114// ErrDataSize is returned if the len(ulid) is different from an encoded 115// ULID's length. Invalid encodings produce undefined ULIDs. For a version that 116// returns an error instead, see ParseStrict. 117func Parse(ulid string) (id ULID, err error) { 118 return id, parse([]byte(ulid), false, &id) 119} 120 121// ParseStrict parses an encoded ULID, returning an error in case of failure. 122// 123// It is like Parse, but additionally validates that the parsed ULID consists 124// only of valid base32 characters. It is slightly slower than Parse. 125// 126// ErrDataSize is returned if the len(ulid) is different from an encoded 127// ULID's length. Invalid encodings return ErrInvalidCharacters. 128func ParseStrict(ulid string) (id ULID, err error) { 129 return id, parse([]byte(ulid), true, &id) 130} 131 132func parse(v []byte, strict bool, id *ULID) error { 133 // Check if a base32 encoded ULID is the right length. 134 if len(v) != EncodedSize { 135 return ErrDataSize 136 } 137 138 // Check if all the characters in a base32 encoded ULID are part of the 139 // expected base32 character set. 140 if strict && 141 (dec[v[0]] == 0xFF || 142 dec[v[1]] == 0xFF || 143 dec[v[2]] == 0xFF || 144 dec[v[3]] == 0xFF || 145 dec[v[4]] == 0xFF || 146 dec[v[5]] == 0xFF || 147 dec[v[6]] == 0xFF || 148 dec[v[7]] == 0xFF || 149 dec[v[8]] == 0xFF || 150 dec[v[9]] == 0xFF || 151 dec[v[10]] == 0xFF || 152 dec[v[11]] == 0xFF || 153 dec[v[12]] == 0xFF || 154 dec[v[13]] == 0xFF || 155 dec[v[14]] == 0xFF || 156 dec[v[15]] == 0xFF || 157 dec[v[16]] == 0xFF || 158 dec[v[17]] == 0xFF || 159 dec[v[18]] == 0xFF || 160 dec[v[19]] == 0xFF || 161 dec[v[20]] == 0xFF || 162 dec[v[21]] == 0xFF || 163 dec[v[22]] == 0xFF || 164 dec[v[23]] == 0xFF || 165 dec[v[24]] == 0xFF || 166 dec[v[25]] == 0xFF) { 167 return ErrInvalidCharacters 168 } 169 170 // Check if the first character in a base32 encoded ULID will overflow. This 171 // happens because the base32 representation encodes 130 bits, while the 172 // ULID is only 128 bits. 173 // 174 // See https://github.com/oklog/ulid/issues/9 for details. 175 if v[0] > '7' { 176 return ErrOverflow 177 } 178 179 // Use an optimized unrolled loop (from https://github.com/RobThree/NUlid) 180 // to decode a base32 ULID. 181 182 // 6 bytes timestamp (48 bits) 183 (*id)[0] = ((dec[v[0]] << 5) | dec[v[1]]) 184 (*id)[1] = ((dec[v[2]] << 3) | (dec[v[3]] >> 2)) 185 (*id)[2] = ((dec[v[3]] << 6) | (dec[v[4]] << 1) | (dec[v[5]] >> 4)) 186 (*id)[3] = ((dec[v[5]] << 4) | (dec[v[6]] >> 1)) 187 (*id)[4] = ((dec[v[6]] << 7) | (dec[v[7]] << 2) | (dec[v[8]] >> 3)) 188 (*id)[5] = ((dec[v[8]] << 5) | dec[v[9]]) 189 190 // 10 bytes of entropy (80 bits) 191 (*id)[6] = ((dec[v[10]] << 3) | (dec[v[11]] >> 2)) 192 (*id)[7] = ((dec[v[11]] << 6) | (dec[v[12]] << 1) | (dec[v[13]] >> 4)) 193 (*id)[8] = ((dec[v[13]] << 4) | (dec[v[14]] >> 1)) 194 (*id)[9] = ((dec[v[14]] << 7) | (dec[v[15]] << 2) | (dec[v[16]] >> 3)) 195 (*id)[10] = ((dec[v[16]] << 5) | dec[v[17]]) 196 (*id)[11] = ((dec[v[18]] << 3) | dec[v[19]]>>2) 197 (*id)[12] = ((dec[v[19]] << 6) | (dec[v[20]] << 1) | (dec[v[21]] >> 4)) 198 (*id)[13] = ((dec[v[21]] << 4) | (dec[v[22]] >> 1)) 199 (*id)[14] = ((dec[v[22]] << 7) | (dec[v[23]] << 2) | (dec[v[24]] >> 3)) 200 (*id)[15] = ((dec[v[24]] << 5) | dec[v[25]]) 201 202 return nil 203} 204 205// MustParse is a convenience function equivalent to Parse that panics on failure 206// instead of returning an error. 207func MustParse(ulid string) ULID { 208 id, err := Parse(ulid) 209 if err != nil { 210 panic(err) 211 } 212 return id 213} 214 215// MustParseStrict is a convenience function equivalent to ParseStrict that 216// panics on failure instead of returning an error. 217func MustParseStrict(ulid string) ULID { 218 id, err := ParseStrict(ulid) 219 if err != nil { 220 panic(err) 221 } 222 return id 223} 224 225// String returns a lexicographically sortable string encoded ULID 226// (26 characters, non-standard base 32) e.g. 01AN4Z07BY79KA1307SR9X4MV3 227// Format: tttttttttteeeeeeeeeeeeeeee where t is time and e is entropy 228func (id ULID) String() string { 229 ulid := make([]byte, EncodedSize) 230 _ = id.MarshalTextTo(ulid) 231 return string(ulid) 232} 233 234// MarshalBinary implements the encoding.BinaryMarshaler interface by 235// returning the ULID as a byte slice. 236func (id ULID) MarshalBinary() ([]byte, error) { 237 ulid := make([]byte, len(id)) 238 return ulid, id.MarshalBinaryTo(ulid) 239} 240 241// MarshalBinaryTo writes the binary encoding of the ULID to the given buffer. 242// ErrBufferSize is returned when the len(dst) != 16. 243func (id ULID) MarshalBinaryTo(dst []byte) error { 244 if len(dst) != len(id) { 245 return ErrBufferSize 246 } 247 248 copy(dst, id[:]) 249 return nil 250} 251 252// UnmarshalBinary implements the encoding.BinaryUnmarshaler interface by 253// copying the passed data and converting it to an ULID. ErrDataSize is 254// returned if the data length is different from ULID length. 255func (id *ULID) UnmarshalBinary(data []byte) error { 256 if len(data) != len(*id) { 257 return ErrDataSize 258 } 259 260 copy((*id)[:], data) 261 return nil 262} 263 264// Encoding is the base 32 encoding alphabet used in ULID strings. 265const Encoding = "0123456789ABCDEFGHJKMNPQRSTVWXYZ" 266 267// MarshalText implements the encoding.TextMarshaler interface by 268// returning the string encoded ULID. 269func (id ULID) MarshalText() ([]byte, error) { 270 ulid := make([]byte, EncodedSize) 271 return ulid, id.MarshalTextTo(ulid) 272} 273 274// MarshalTextTo writes the ULID as a string to the given buffer. 275// ErrBufferSize is returned when the len(dst) != 26. 276func (id ULID) MarshalTextTo(dst []byte) error { 277 // Optimized unrolled loop ahead. 278 // From https://github.com/RobThree/NUlid 279 280 if len(dst) != EncodedSize { 281 return ErrBufferSize 282 } 283 284 // 10 byte timestamp 285 dst[0] = Encoding[(id[0]&224)>>5] 286 dst[1] = Encoding[id[0]&31] 287 dst[2] = Encoding[(id[1]&248)>>3] 288 dst[3] = Encoding[((id[1]&7)<<2)|((id[2]&192)>>6)] 289 dst[4] = Encoding[(id[2]&62)>>1] 290 dst[5] = Encoding[((id[2]&1)<<4)|((id[3]&240)>>4)] 291 dst[6] = Encoding[((id[3]&15)<<1)|((id[4]&128)>>7)] 292 dst[7] = Encoding[(id[4]&124)>>2] 293 dst[8] = Encoding[((id[4]&3)<<3)|((id[5]&224)>>5)] 294 dst[9] = Encoding[id[5]&31] 295 296 // 16 bytes of entropy 297 dst[10] = Encoding[(id[6]&248)>>3] 298 dst[11] = Encoding[((id[6]&7)<<2)|((id[7]&192)>>6)] 299 dst[12] = Encoding[(id[7]&62)>>1] 300 dst[13] = Encoding[((id[7]&1)<<4)|((id[8]&240)>>4)] 301 dst[14] = Encoding[((id[8]&15)<<1)|((id[9]&128)>>7)] 302 dst[15] = Encoding[(id[9]&124)>>2] 303 dst[16] = Encoding[((id[9]&3)<<3)|((id[10]&224)>>5)] 304 dst[17] = Encoding[id[10]&31] 305 dst[18] = Encoding[(id[11]&248)>>3] 306 dst[19] = Encoding[((id[11]&7)<<2)|((id[12]&192)>>6)] 307 dst[20] = Encoding[(id[12]&62)>>1] 308 dst[21] = Encoding[((id[12]&1)<<4)|((id[13]&240)>>4)] 309 dst[22] = Encoding[((id[13]&15)<<1)|((id[14]&128)>>7)] 310 dst[23] = Encoding[(id[14]&124)>>2] 311 dst[24] = Encoding[((id[14]&3)<<3)|((id[15]&224)>>5)] 312 dst[25] = Encoding[id[15]&31] 313 314 return nil 315} 316 317// Byte to index table for O(1) lookups when unmarshaling. 318// We use 0xFF as sentinel value for invalid indexes. 319var dec = [...]byte{ 320 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 321 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 322 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 323 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 324 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x01, 325 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0xFF, 0xFF, 326 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 327 0x0F, 0x10, 0x11, 0xFF, 0x12, 0x13, 0xFF, 0x14, 0x15, 0xFF, 328 0x16, 0x17, 0x18, 0x19, 0x1A, 0xFF, 0x1B, 0x1C, 0x1D, 0x1E, 329 0x1F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x0A, 0x0B, 0x0C, 330 0x0D, 0x0E, 0x0F, 0x10, 0x11, 0xFF, 0x12, 0x13, 0xFF, 0x14, 331 0x15, 0xFF, 0x16, 0x17, 0x18, 0x19, 0x1A, 0xFF, 0x1B, 0x1C, 332 0x1D, 0x1E, 0x1F, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 333 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 334 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 335 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 336 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 337 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 338 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 339 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 340 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 341 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 342 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 343 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 344 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 345 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 346} 347 348// EncodedSize is the length of a text encoded ULID. 349const EncodedSize = 26 350 351// UnmarshalText implements the encoding.TextUnmarshaler interface by 352// parsing the data as string encoded ULID. 353// 354// ErrDataSize is returned if the len(v) is different from an encoded 355// ULID's length. Invalid encodings produce undefined ULIDs. 356func (id *ULID) UnmarshalText(v []byte) error { 357 return parse(v, false, id) 358} 359 360// Time returns the Unix time in milliseconds encoded in the ULID. 361// Use the top level Time function to convert the returned value to 362// a time.Time. 363func (id ULID) Time() uint64 { 364 return uint64(id[5]) | uint64(id[4])<<8 | 365 uint64(id[3])<<16 | uint64(id[2])<<24 | 366 uint64(id[1])<<32 | uint64(id[0])<<40 367} 368 369// maxTime is the maximum Unix time in milliseconds that can be 370// represented in an ULID. 371var maxTime = ULID{0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}.Time() 372 373// MaxTime returns the maximum Unix time in milliseconds that 374// can be encoded in an ULID. 375func MaxTime() uint64 { return maxTime } 376 377// Now is a convenience function that returns the current 378// UTC time in Unix milliseconds. Equivalent to: 379// Timestamp(time.Now().UTC()) 380func Now() uint64 { return Timestamp(time.Now().UTC()) } 381 382// Timestamp converts a time.Time to Unix milliseconds. 383// 384// Because of the way ULID stores time, times from the year 385// 10889 produces undefined results. 386func Timestamp(t time.Time) uint64 { 387 return uint64(t.Unix())*1000 + 388 uint64(t.Nanosecond()/int(time.Millisecond)) 389} 390 391// Time converts Unix milliseconds in the format 392// returned by the Timestamp function to a time.Time. 393func Time(ms uint64) time.Time { 394 s := int64(ms / 1e3) 395 ns := int64((ms % 1e3) * 1e6) 396 return time.Unix(s, ns) 397} 398 399// SetTime sets the time component of the ULID to the given Unix time 400// in milliseconds. 401func (id *ULID) SetTime(ms uint64) error { 402 if ms > maxTime { 403 return ErrBigTime 404 } 405 406 (*id)[0] = byte(ms >> 40) 407 (*id)[1] = byte(ms >> 32) 408 (*id)[2] = byte(ms >> 24) 409 (*id)[3] = byte(ms >> 16) 410 (*id)[4] = byte(ms >> 8) 411 (*id)[5] = byte(ms) 412 413 return nil 414} 415 416// Entropy returns the entropy from the ULID. 417func (id ULID) Entropy() []byte { 418 e := make([]byte, 10) 419 copy(e, id[6:]) 420 return e 421} 422 423// SetEntropy sets the ULID entropy to the passed byte slice. 424// ErrDataSize is returned if len(e) != 10. 425func (id *ULID) SetEntropy(e []byte) error { 426 if len(e) != 10 { 427 return ErrDataSize 428 } 429 430 copy((*id)[6:], e) 431 return nil 432} 433 434// Compare returns an integer comparing id and other lexicographically. 435// The result will be 0 if id==other, -1 if id < other, and +1 if id > other. 436func (id ULID) Compare(other ULID) int { 437 return bytes.Compare(id[:], other[:]) 438} 439 440// Scan implements the sql.Scanner interface. It supports scanning 441// a string or byte slice. 442func (id *ULID) Scan(src interface{}) error { 443 switch x := src.(type) { 444 case nil: 445 return nil 446 case string: 447 return id.UnmarshalText([]byte(x)) 448 case []byte: 449 return id.UnmarshalBinary(x) 450 } 451 452 return ErrScanValue 453} 454 455// Value implements the sql/driver.Valuer interface. This returns the value 456// represented as a byte slice. If instead a string is desirable, a wrapper 457// type can be created that calls String(). 458// 459// // stringValuer wraps a ULID as a string-based driver.Valuer. 460// type stringValuer ULID 461// 462// func (id stringValuer) Value() (driver.Value, error) { 463// return ULID(id).String(), nil 464// } 465// 466// // Example usage. 467// db.Exec("...", stringValuer(id)) 468func (id ULID) Value() (driver.Value, error) { 469 return id.MarshalBinary() 470} 471 472// Monotonic returns an entropy source that is guaranteed to yield 473// strictly increasing entropy bytes for the same ULID timestamp. 474// On conflicts, the previous ULID entropy is incremented with a 475// random number between 1 and `inc` (inclusive). 476// 477// The provided entropy source must actually yield random bytes or else 478// monotonic reads are not guaranteed to terminate, since there isn't 479// enough randomness to compute an increment number. 480// 481// When `inc == 0`, it'll be set to a secure default of `math.MaxUint32`. 482// The lower the value of `inc`, the easier the next ULID within the 483// same millisecond is to guess. If your code depends on ULIDs having 484// secure entropy bytes, then don't go under this default unless you know 485// what you're doing. 486// 487// The returned io.Reader isn't safe for concurrent use. 488func Monotonic(entropy io.Reader, inc uint64) io.Reader { 489 m := monotonic{ 490 Reader: bufio.NewReader(entropy), 491 inc: inc, 492 } 493 494 if m.inc == 0 { 495 m.inc = math.MaxUint32 496 } 497 498 if rng, ok := entropy.(*rand.Rand); ok { 499 m.rng = rng 500 } 501 502 return &m 503} 504 505type monotonic struct { 506 io.Reader 507 ms uint64 508 inc uint64 509 entropy uint80 510 rand [8]byte 511 rng *rand.Rand 512} 513 514func (m *monotonic) MonotonicRead(ms uint64, entropy []byte) (err error) { 515 if !m.entropy.IsZero() && m.ms == ms { 516 err = m.increment() 517 m.entropy.AppendTo(entropy) 518 } else if _, err = io.ReadFull(m.Reader, entropy); err == nil { 519 m.ms = ms 520 m.entropy.SetBytes(entropy) 521 } 522 return err 523} 524 525// increment the previous entropy number with a random number 526// of up to m.inc (inclusive). 527func (m *monotonic) increment() error { 528 if inc, err := m.random(); err != nil { 529 return err 530 } else if m.entropy.Add(inc) { 531 return ErrMonotonicOverflow 532 } 533 return nil 534} 535 536// random returns a uniform random value in [1, m.inc), reading entropy 537// from m.Reader. When m.inc == 0 || m.inc == 1, it returns 1. 538// Adapted from: https://golang.org/pkg/crypto/rand/#Int 539func (m *monotonic) random() (inc uint64, err error) { 540 if m.inc <= 1 { 541 return 1, nil 542 } 543 544 // Fast path for using a underlying rand.Rand directly. 545 if m.rng != nil { 546 // Range: [1, m.inc) 547 return 1 + uint64(m.rng.Int63n(int64(m.inc))), nil 548 } 549 550 // bitLen is the maximum bit length needed to encode a value < m.inc. 551 bitLen := bits.Len64(m.inc) 552 553 // byteLen is the maximum byte length needed to encode a value < m.inc. 554 byteLen := uint(bitLen+7) / 8 555 556 // msbitLen is the number of bits in the most significant byte of m.inc-1. 557 msbitLen := uint(bitLen % 8) 558 if msbitLen == 0 { 559 msbitLen = 8 560 } 561 562 for inc == 0 || inc >= m.inc { 563 if _, err = io.ReadFull(m.Reader, m.rand[:byteLen]); err != nil { 564 return 0, err 565 } 566 567 // Clear bits in the first byte to increase the probability 568 // that the candidate is < m.inc. 569 m.rand[0] &= uint8(int(1<<msbitLen) - 1) 570 571 // Convert the read bytes into an uint64 with byteLen 572 // Optimized unrolled loop. 573 switch byteLen { 574 case 1: 575 inc = uint64(m.rand[0]) 576 case 2: 577 inc = uint64(binary.LittleEndian.Uint16(m.rand[:2])) 578 case 3, 4: 579 inc = uint64(binary.LittleEndian.Uint32(m.rand[:4])) 580 case 5, 6, 7, 8: 581 inc = uint64(binary.LittleEndian.Uint64(m.rand[:8])) 582 } 583 } 584 585 // Range: [1, m.inc) 586 return 1 + inc, nil 587} 588 589type uint80 struct { 590 Hi uint16 591 Lo uint64 592} 593 594func (u *uint80) SetBytes(bs []byte) { 595 u.Hi = binary.BigEndian.Uint16(bs[:2]) 596 u.Lo = binary.BigEndian.Uint64(bs[2:]) 597} 598 599func (u *uint80) AppendTo(bs []byte) { 600 binary.BigEndian.PutUint16(bs[:2], u.Hi) 601 binary.BigEndian.PutUint64(bs[2:], u.Lo) 602} 603 604func (u *uint80) Add(n uint64) (overflow bool) { 605 lo, hi := u.Lo, u.Hi 606 if u.Lo += n; u.Lo < lo { 607 u.Hi++ 608 } 609 return u.Hi < hi 610} 611 612func (u uint80) IsZero() bool { 613 return u.Hi == 0 && u.Lo == 0 614} 615