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