podman

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

14
package ulid
15

16
import (
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
/*
30
An 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
*/
47
type ULID [16]byte
48

49
var (
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.
85
func 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.
104
func 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.
117
func 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.
128
func ParseStrict(ulid string) (id ULID, err error) {
129
	return id, parse([]byte(ulid), true, &id)
130
}
131

132
func 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.
207
func 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.
217
func 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
228
func (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.
236
func (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.
243
func (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.
255
func (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.
265
const Encoding = "0123456789ABCDEFGHJKMNPQRSTVWXYZ"
266

267
// MarshalText implements the encoding.TextMarshaler interface by
268
// returning the string encoded ULID.
269
func (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.
276
func (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.
319
var 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.
349
const 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.
356
func (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.
363
func (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.
371
var 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.
375
func 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())
380
func 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.
386
func 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.
393
func 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.
401
func (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.
417
func (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.
425
func (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.
436
func (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.
442
func (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))
468
func (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.
488
func 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

505
type monotonic struct {
506
	io.Reader
507
	ms      uint64
508
	inc     uint64
509
	entropy uint80
510
	rand    [8]byte
511
	rng     *rand.Rand
512
}
513

514
func (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).
527
func (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
539
func (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

589
type uint80 struct {
590
	Hi uint16
591
	Lo uint64
592
}
593

594
func (u *uint80) SetBytes(bs []byte) {
595
	u.Hi = binary.BigEndian.Uint16(bs[:2])
596
	u.Lo = binary.BigEndian.Uint64(bs[2:])
597
}
598

599
func (u *uint80) AppendTo(bs []byte) {
600
	binary.BigEndian.PutUint16(bs[:2], u.Hi)
601
	binary.BigEndian.PutUint64(bs[2:], u.Lo)
602
}
603

604
func (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

612
func (u uint80) IsZero() bool {
613
	return u.Hi == 0 && u.Lo == 0
614
}
615