1 | /**
|
2 | * Efficient schema-less binary decoding with support for variable length encoding.
|
3 | *
|
4 | * Use [lib0/decoding] with [lib0/encoding]. Every encoding function has a corresponding decoding function.
|
5 | *
|
6 | * Encodes numbers in little-endian order (least to most significant byte order)
|
7 | * and is compatible with Golang's binary encoding (https://golang.org/pkg/encoding/binary/)
|
8 | * which is also used in Protocol Buffers.
|
9 | *
|
10 | * ```js
|
11 | * // encoding step
|
12 | * const encoder = new encoding.createEncoder()
|
13 | * encoding.writeVarUint(encoder, 256)
|
14 | * encoding.writeVarString(encoder, 'Hello world!')
|
15 | * const buf = encoding.toUint8Array(encoder)
|
16 | * ```
|
17 | *
|
18 | * ```js
|
19 | * // decoding step
|
20 | * const decoder = new decoding.createDecoder(buf)
|
21 | * decoding.readVarUint(decoder) // => 256
|
22 | * decoding.readVarString(decoder) // => 'Hello world!'
|
23 | * decoding.hasContent(decoder) // => false - all data is read
|
24 | * ```
|
25 | *
|
26 | * @module decoding
|
27 | */
|
28 |
|
29 | import * as buffer from './buffer.js'
|
30 | import * as binary from './binary.js'
|
31 | import * as math from './math.js'
|
32 | import * as number from './number.js'
|
33 | import * as string from './string.js'
|
34 |
|
35 | /**
|
36 | * A Decoder handles the decoding of an Uint8Array.
|
37 | */
|
38 | export class Decoder {
|
39 | /**
|
40 | * @param {Uint8Array} uint8Array Binary data to decode
|
41 | */
|
42 | constructor (uint8Array) {
|
43 | /**
|
44 | * Decoding target.
|
45 | *
|
46 | * @type {Uint8Array}
|
47 | */
|
48 | this.arr = uint8Array
|
49 | /**
|
50 | * Current decoding position.
|
51 | *
|
52 | * @type {number}
|
53 | */
|
54 | this.pos = 0
|
55 | }
|
56 | }
|
57 |
|
58 | /**
|
59 | * @function
|
60 | * @param {Uint8Array} uint8Array
|
61 | * @return {Decoder}
|
62 | */
|
63 | export const createDecoder = uint8Array => new Decoder(uint8Array)
|
64 |
|
65 | /**
|
66 | * @function
|
67 | * @param {Decoder} decoder
|
68 | * @return {boolean}
|
69 | */
|
70 | export const hasContent = decoder => decoder.pos !== decoder.arr.length
|
71 |
|
72 | /**
|
73 | * Clone a decoder instance.
|
74 | * Optionally set a new position parameter.
|
75 | *
|
76 | * @function
|
77 | * @param {Decoder} decoder The decoder instance
|
78 | * @param {number} [newPos] Defaults to current position
|
79 | * @return {Decoder} A clone of `decoder`
|
80 | */
|
81 | export const clone = (decoder, newPos = decoder.pos) => {
|
82 | const _decoder = createDecoder(decoder.arr)
|
83 | _decoder.pos = newPos
|
84 | return _decoder
|
85 | }
|
86 |
|
87 | /**
|
88 | * Create an Uint8Array view of the next `len` bytes and advance the position by `len`.
|
89 | *
|
90 | * Important: The Uint8Array still points to the underlying ArrayBuffer. Make sure to discard the result as soon as possible to prevent any memory leaks.
|
91 | * Use `buffer.copyUint8Array` to copy the result into a new Uint8Array.
|
92 | *
|
93 | * @function
|
94 | * @param {Decoder} decoder The decoder instance
|
95 | * @param {number} len The length of bytes to read
|
96 | * @return {Uint8Array}
|
97 | */
|
98 | export const readUint8Array = (decoder, len) => {
|
99 | const view = buffer.createUint8ArrayViewFromArrayBuffer(decoder.arr.buffer, decoder.pos + decoder.arr.byteOffset, len)
|
100 | decoder.pos += len
|
101 | return view
|
102 | }
|
103 |
|
104 | /**
|
105 | * Read variable length Uint8Array.
|
106 | *
|
107 | * Important: The Uint8Array still points to the underlying ArrayBuffer. Make sure to discard the result as soon as possible to prevent any memory leaks.
|
108 | * Use `buffer.copyUint8Array` to copy the result into a new Uint8Array.
|
109 | *
|
110 | * @function
|
111 | * @param {Decoder} decoder
|
112 | * @return {Uint8Array}
|
113 | */
|
114 | export const readVarUint8Array = decoder => readUint8Array(decoder, readVarUint(decoder))
|
115 |
|
116 | /**
|
117 | * Read the rest of the content as an ArrayBuffer
|
118 | * @function
|
119 | * @param {Decoder} decoder
|
120 | * @return {Uint8Array}
|
121 | */
|
122 | export const readTailAsUint8Array = decoder => readUint8Array(decoder, decoder.arr.length - decoder.pos)
|
123 |
|
124 | /**
|
125 | * Skip one byte, jump to the next position.
|
126 | * @function
|
127 | * @param {Decoder} decoder The decoder instance
|
128 | * @return {number} The next position
|
129 | */
|
130 | export const skip8 = decoder => decoder.pos++
|
131 |
|
132 | /**
|
133 | * Read one byte as unsigned integer.
|
134 | * @function
|
135 | * @param {Decoder} decoder The decoder instance
|
136 | * @return {number} Unsigned 8-bit integer
|
137 | */
|
138 | export const readUint8 = decoder => decoder.arr[decoder.pos++]
|
139 |
|
140 | /**
|
141 | * Read 2 bytes as unsigned integer.
|
142 | *
|
143 | * @function
|
144 | * @param {Decoder} decoder
|
145 | * @return {number} An unsigned integer.
|
146 | */
|
147 | export const readUint16 = decoder => {
|
148 | const uint =
|
149 | decoder.arr[decoder.pos] +
|
150 | (decoder.arr[decoder.pos + 1] << 8)
|
151 | decoder.pos += 2
|
152 | return uint
|
153 | }
|
154 |
|
155 | /**
|
156 | * Read 4 bytes as unsigned integer.
|
157 | *
|
158 | * @function
|
159 | * @param {Decoder} decoder
|
160 | * @return {number} An unsigned integer.
|
161 | */
|
162 | export const readUint32 = decoder => {
|
163 | const uint =
|
164 | (decoder.arr[decoder.pos] +
|
165 | (decoder.arr[decoder.pos + 1] << 8) +
|
166 | (decoder.arr[decoder.pos + 2] << 16) +
|
167 | (decoder.arr[decoder.pos + 3] << 24)) >>> 0
|
168 | decoder.pos += 4
|
169 | return uint
|
170 | }
|
171 |
|
172 | /**
|
173 | * Read 4 bytes as unsigned integer in big endian order.
|
174 | * (most significant byte first)
|
175 | *
|
176 | * @function
|
177 | * @param {Decoder} decoder
|
178 | * @return {number} An unsigned integer.
|
179 | */
|
180 | export const readUint32BigEndian = decoder => {
|
181 | const uint =
|
182 | (decoder.arr[decoder.pos + 3] +
|
183 | (decoder.arr[decoder.pos + 2] << 8) +
|
184 | (decoder.arr[decoder.pos + 1] << 16) +
|
185 | (decoder.arr[decoder.pos] << 24)) >>> 0
|
186 | decoder.pos += 4
|
187 | return uint
|
188 | }
|
189 |
|
190 | /**
|
191 | * Look ahead without incrementing the position
|
192 | * to the next byte and read it as unsigned integer.
|
193 | *
|
194 | * @function
|
195 | * @param {Decoder} decoder
|
196 | * @return {number} An unsigned integer.
|
197 | */
|
198 | export const peekUint8 = decoder => decoder.arr[decoder.pos]
|
199 |
|
200 | /**
|
201 | * Look ahead without incrementing the position
|
202 | * to the next byte and read it as unsigned integer.
|
203 | *
|
204 | * @function
|
205 | * @param {Decoder} decoder
|
206 | * @return {number} An unsigned integer.
|
207 | */
|
208 | export const peekUint16 = decoder =>
|
209 | decoder.arr[decoder.pos] +
|
210 | (decoder.arr[decoder.pos + 1] << 8)
|
211 |
|
212 | /**
|
213 | * Look ahead without incrementing the position
|
214 | * to the next byte and read it as unsigned integer.
|
215 | *
|
216 | * @function
|
217 | * @param {Decoder} decoder
|
218 | * @return {number} An unsigned integer.
|
219 | */
|
220 | export const peekUint32 = decoder => (
|
221 | decoder.arr[decoder.pos] +
|
222 | (decoder.arr[decoder.pos + 1] << 8) +
|
223 | (decoder.arr[decoder.pos + 2] << 16) +
|
224 | (decoder.arr[decoder.pos + 3] << 24)
|
225 | ) >>> 0
|
226 |
|
227 | /**
|
228 | * Read unsigned integer (32bit) with variable length.
|
229 | * 1/8th of the storage is used as encoding overhead.
|
230 | * * numbers < 2^7 is stored in one bytlength
|
231 | * * numbers < 2^14 is stored in two bylength
|
232 | *
|
233 | * @function
|
234 | * @param {Decoder} decoder
|
235 | * @return {number} An unsigned integer.length
|
236 | */
|
237 | export const readVarUint = decoder => {
|
238 | let num = 0
|
239 | let mult = 1
|
240 | while (true) {
|
241 | const r = decoder.arr[decoder.pos++]
|
242 | // num = num | ((r & binary.BITS7) << len)
|
243 | num = num + (r & binary.BITS7) * mult // shift $r << (7*#iterations) and add it to num
|
244 | mult *= 128 // next iteration, shift 7 "more" to the left
|
245 | if (r < binary.BIT8) {
|
246 | return num
|
247 | }
|
248 | /* istanbul ignore if */
|
249 | if (num > number.MAX_SAFE_INTEGER) {
|
250 | throw new Error('Integer out of range!')
|
251 | }
|
252 | }
|
253 | }
|
254 |
|
255 | /**
|
256 | * Read signed integer (32bit) with variable length.
|
257 | * 1/8th of the storage is used as encoding overhead.
|
258 | * * numbers < 2^7 is stored in one bytlength
|
259 | * * numbers < 2^14 is stored in two bylength
|
260 | * @todo This should probably create the inverse ~num if number is negative - but this would be a breaking change.
|
261 | *
|
262 | * @function
|
263 | * @param {Decoder} decoder
|
264 | * @return {number} An unsigned integer.length
|
265 | */
|
266 | export const readVarInt = decoder => {
|
267 | let r = decoder.arr[decoder.pos++]
|
268 | let num = r & binary.BITS6
|
269 | let mult = 64
|
270 | const sign = (r & binary.BIT7) > 0 ? -1 : 1
|
271 | if ((r & binary.BIT8) === 0) {
|
272 | // don't continue reading
|
273 | return sign * num
|
274 | }
|
275 | while (true) {
|
276 | r = decoder.arr[decoder.pos++]
|
277 | // num = num | ((r & binary.BITS7) << len)
|
278 | num = num + (r & binary.BITS7) * mult
|
279 | mult *= 128
|
280 | if (r < binary.BIT8) {
|
281 | return sign * num
|
282 | }
|
283 | /* istanbul ignore if */
|
284 | if (num > number.MAX_SAFE_INTEGER) {
|
285 | throw new Error('Integer out of range!')
|
286 | }
|
287 | }
|
288 | }
|
289 |
|
290 | /**
|
291 | * Look ahead and read varUint without incrementing position
|
292 | *
|
293 | * @function
|
294 | * @param {Decoder} decoder
|
295 | * @return {number}
|
296 | */
|
297 | export const peekVarUint = decoder => {
|
298 | const pos = decoder.pos
|
299 | const s = readVarUint(decoder)
|
300 | decoder.pos = pos
|
301 | return s
|
302 | }
|
303 |
|
304 | /**
|
305 | * Look ahead and read varUint without incrementing position
|
306 | *
|
307 | * @function
|
308 | * @param {Decoder} decoder
|
309 | * @return {number}
|
310 | */
|
311 | export const peekVarInt = decoder => {
|
312 | const pos = decoder.pos
|
313 | const s = readVarInt(decoder)
|
314 | decoder.pos = pos
|
315 | return s
|
316 | }
|
317 |
|
318 | /**
|
319 | * We don't test this function anymore as we use native decoding/encoding by default now.
|
320 | * Better not modify this anymore..
|
321 | *
|
322 | * Transforming utf8 to a string is pretty expensive. The code performs 10x better
|
323 | * when String.fromCodePoint is fed with all characters as arguments.
|
324 | * But most environments have a maximum number of arguments per functions.
|
325 | * For effiency reasons we apply a maximum of 10000 characters at once.
|
326 | *
|
327 | * @function
|
328 | * @param {Decoder} decoder
|
329 | * @return {String} The read String.
|
330 | */
|
331 | /* istanbul ignore next */
|
332 | export const _readVarStringPolyfill = decoder => {
|
333 | let remainingLen = readVarUint(decoder)
|
334 | if (remainingLen === 0) {
|
335 | return ''
|
336 | } else {
|
337 | let encodedString = String.fromCodePoint(readUint8(decoder)) // remember to decrease remainingLen
|
338 | if (--remainingLen < 100) { // do not create a Uint8Array for small strings
|
339 | while (remainingLen--) {
|
340 | encodedString += String.fromCodePoint(readUint8(decoder))
|
341 | }
|
342 | } else {
|
343 | while (remainingLen > 0) {
|
344 | const nextLen = remainingLen < 10000 ? remainingLen : 10000
|
345 | // this is dangerous, we create a fresh array view from the existing buffer
|
346 | const bytes = decoder.arr.subarray(decoder.pos, decoder.pos + nextLen)
|
347 | decoder.pos += nextLen
|
348 | // Starting with ES5.1 we can supply a generic array-like object as arguments
|
349 | encodedString += String.fromCodePoint.apply(null, /** @type {any} */ (bytes))
|
350 | remainingLen -= nextLen
|
351 | }
|
352 | }
|
353 | return decodeURIComponent(escape(encodedString))
|
354 | }
|
355 | }
|
356 |
|
357 | /**
|
358 | * @function
|
359 | * @param {Decoder} decoder
|
360 | * @return {String} The read String
|
361 | */
|
362 | export const _readVarStringNative = decoder =>
|
363 | /** @type any */ (string.utf8TextDecoder).decode(readVarUint8Array(decoder))
|
364 |
|
365 | /**
|
366 | * Read string of variable length
|
367 | * * varUint is used to store the length of the string
|
368 | *
|
369 | * @function
|
370 | * @param {Decoder} decoder
|
371 | * @return {String} The read String
|
372 | *
|
373 | */
|
374 | /* istanbul ignore next */
|
375 | export const readVarString = string.utf8TextDecoder ? _readVarStringNative : _readVarStringPolyfill
|
376 |
|
377 | /**
|
378 | * Look ahead and read varString without incrementing position
|
379 | *
|
380 | * @function
|
381 | * @param {Decoder} decoder
|
382 | * @return {string}
|
383 | */
|
384 | export const peekVarString = decoder => {
|
385 | const pos = decoder.pos
|
386 | const s = readVarString(decoder)
|
387 | decoder.pos = pos
|
388 | return s
|
389 | }
|
390 |
|
391 | /**
|
392 | * @param {Decoder} decoder
|
393 | * @param {number} len
|
394 | * @return {DataView}
|
395 | */
|
396 | export const readFromDataView = (decoder, len) => {
|
397 | const dv = new DataView(decoder.arr.buffer, decoder.arr.byteOffset + decoder.pos, len)
|
398 | decoder.pos += len
|
399 | return dv
|
400 | }
|
401 |
|
402 | /**
|
403 | * @param {Decoder} decoder
|
404 | */
|
405 | export const readFloat32 = decoder => readFromDataView(decoder, 4).getFloat32(0, false)
|
406 |
|
407 | /**
|
408 | * @param {Decoder} decoder
|
409 | */
|
410 | export const readFloat64 = decoder => readFromDataView(decoder, 8).getFloat64(0, false)
|
411 |
|
412 | /**
|
413 | * @param {Decoder} decoder
|
414 | */
|
415 | export const readBigInt64 = decoder => /** @type {any} */ (readFromDataView(decoder, 8)).getBigInt64(0, false)
|
416 |
|
417 | /**
|
418 | * @param {Decoder} decoder
|
419 | */
|
420 | export const readBigUint64 = decoder => /** @type {any} */ (readFromDataView(decoder, 8)).getBigUint64(0, false)
|
421 |
|
422 | /**
|
423 | * @type {Array<function(Decoder):any>}
|
424 | */
|
425 | const readAnyLookupTable = [
|
426 | decoder => undefined, // CASE 127: undefined
|
427 | decoder => null, // CASE 126: null
|
428 | readVarInt, // CASE 125: integer
|
429 | readFloat32, // CASE 124: float32
|
430 | readFloat64, // CASE 123: float64
|
431 | readBigInt64, // CASE 122: bigint
|
432 | decoder => false, // CASE 121: boolean (false)
|
433 | decoder => true, // CASE 120: boolean (true)
|
434 | readVarString, // CASE 119: string
|
435 | decoder => { // CASE 118: object<string,any>
|
436 | const len = readVarUint(decoder)
|
437 | /**
|
438 | * @type {Object<string,any>}
|
439 | */
|
440 | const obj = {}
|
441 | for (let i = 0; i < len; i++) {
|
442 | const key = readVarString(decoder)
|
443 | obj[key] = readAny(decoder)
|
444 | }
|
445 | return obj
|
446 | },
|
447 | decoder => { // CASE 117: array<any>
|
448 | const len = readVarUint(decoder)
|
449 | const arr = []
|
450 | for (let i = 0; i < len; i++) {
|
451 | arr.push(readAny(decoder))
|
452 | }
|
453 | return arr
|
454 | },
|
455 | readVarUint8Array // CASE 116: Uint8Array
|
456 | ]
|
457 |
|
458 | /**
|
459 | * @param {Decoder} decoder
|
460 | */
|
461 | export const readAny = decoder => readAnyLookupTable[127 - readUint8(decoder)](decoder)
|
462 |
|
463 | /**
|
464 | * T must not be null.
|
465 | *
|
466 | * @template T
|
467 | */
|
468 | export class RleDecoder extends Decoder {
|
469 | /**
|
470 | * @param {Uint8Array} uint8Array
|
471 | * @param {function(Decoder):T} reader
|
472 | */
|
473 | constructor (uint8Array, reader) {
|
474 | super(uint8Array)
|
475 | /**
|
476 | * The reader
|
477 | */
|
478 | this.reader = reader
|
479 | /**
|
480 | * Current state
|
481 | * @type {T|null}
|
482 | */
|
483 | this.s = null
|
484 | this.count = 0
|
485 | }
|
486 |
|
487 | read () {
|
488 | if (this.count === 0) {
|
489 | this.s = this.reader(this)
|
490 | if (hasContent(this)) {
|
491 | this.count = readVarUint(this) + 1 // see encoder implementation for the reason why this is incremented
|
492 | } else {
|
493 | this.count = -1 // read the current value forever
|
494 | }
|
495 | }
|
496 | this.count--
|
497 | return /** @type {T} */ (this.s)
|
498 | }
|
499 | }
|
500 |
|
501 | export class IntDiffDecoder extends Decoder {
|
502 | /**
|
503 | * @param {Uint8Array} uint8Array
|
504 | * @param {number} start
|
505 | */
|
506 | constructor (uint8Array, start) {
|
507 | super(uint8Array)
|
508 | /**
|
509 | * Current state
|
510 | * @type {number}
|
511 | */
|
512 | this.s = start
|
513 | }
|
514 |
|
515 | /**
|
516 | * @return {number}
|
517 | */
|
518 | read () {
|
519 | this.s += readVarInt(this)
|
520 | return this.s
|
521 | }
|
522 | }
|
523 |
|
524 | export class RleIntDiffDecoder extends Decoder {
|
525 | /**
|
526 | * @param {Uint8Array} uint8Array
|
527 | * @param {number} start
|
528 | */
|
529 | constructor (uint8Array, start) {
|
530 | super(uint8Array)
|
531 | /**
|
532 | * Current state
|
533 | * @type {number}
|
534 | */
|
535 | this.s = start
|
536 | this.count = 0
|
537 | }
|
538 |
|
539 | /**
|
540 | * @return {number}
|
541 | */
|
542 | read () {
|
543 | if (this.count === 0) {
|
544 | this.s += readVarInt(this)
|
545 | if (hasContent(this)) {
|
546 | this.count = readVarUint(this) + 1 // see encoder implementation for the reason why this is incremented
|
547 | } else {
|
548 | this.count = -1 // read the current value forever
|
549 | }
|
550 | }
|
551 | this.count--
|
552 | return /** @type {number} */ (this.s)
|
553 | }
|
554 | }
|
555 |
|
556 | export class UintOptRleDecoder extends Decoder {
|
557 | /**
|
558 | * @param {Uint8Array} uint8Array
|
559 | */
|
560 | constructor (uint8Array) {
|
561 | super(uint8Array)
|
562 | /**
|
563 | * @type {number}
|
564 | */
|
565 | this.s = 0
|
566 | this.count = 0
|
567 | }
|
568 |
|
569 | read () {
|
570 | if (this.count === 0) {
|
571 | this.s = readVarInt(this)
|
572 | // if the sign is negative, we read the count too, otherwise count is 1
|
573 | const isNegative = math.isNegativeZero(this.s)
|
574 | this.count = 1
|
575 | if (isNegative) {
|
576 | this.s = -this.s
|
577 | this.count = readVarUint(this) + 2
|
578 | }
|
579 | }
|
580 | this.count--
|
581 | return /** @type {number} */ (this.s)
|
582 | }
|
583 | }
|
584 |
|
585 | export class IncUintOptRleDecoder extends Decoder {
|
586 | /**
|
587 | * @param {Uint8Array} uint8Array
|
588 | */
|
589 | constructor (uint8Array) {
|
590 | super(uint8Array)
|
591 | /**
|
592 | * @type {number}
|
593 | */
|
594 | this.s = 0
|
595 | this.count = 0
|
596 | }
|
597 |
|
598 | read () {
|
599 | if (this.count === 0) {
|
600 | this.s = readVarInt(this)
|
601 | // if the sign is negative, we read the count too, otherwise count is 1
|
602 | const isNegative = math.isNegativeZero(this.s)
|
603 | this.count = 1
|
604 | if (isNegative) {
|
605 | this.s = -this.s
|
606 | this.count = readVarUint(this) + 2
|
607 | }
|
608 | }
|
609 | this.count--
|
610 | return /** @type {number} */ (this.s++)
|
611 | }
|
612 | }
|
613 |
|
614 | export class IntDiffOptRleDecoder extends Decoder {
|
615 | /**
|
616 | * @param {Uint8Array} uint8Array
|
617 | */
|
618 | constructor (uint8Array) {
|
619 | super(uint8Array)
|
620 | /**
|
621 | * @type {number}
|
622 | */
|
623 | this.s = 0
|
624 | this.count = 0
|
625 | this.diff = 0
|
626 | }
|
627 |
|
628 | /**
|
629 | * @return {number}
|
630 | */
|
631 | read () {
|
632 | if (this.count === 0) {
|
633 | const diff = readVarInt(this)
|
634 | // if the first bit is set, we read more data
|
635 | const hasCount = diff & 1
|
636 | this.diff = math.floor(diff / 2) // shift >> 1
|
637 | this.count = 1
|
638 | if (hasCount) {
|
639 | this.count = readVarUint(this) + 2
|
640 | }
|
641 | }
|
642 | this.s += this.diff
|
643 | this.count--
|
644 | return this.s
|
645 | }
|
646 | }
|
647 |
|
648 | export class StringDecoder {
|
649 | /**
|
650 | * @param {Uint8Array} uint8Array
|
651 | */
|
652 | constructor (uint8Array) {
|
653 | this.decoder = new UintOptRleDecoder(uint8Array)
|
654 | this.str = readVarString(this.decoder)
|
655 | /**
|
656 | * @type {number}
|
657 | */
|
658 | this.spos = 0
|
659 | }
|
660 |
|
661 | /**
|
662 | * @return {string}
|
663 | */
|
664 | read () {
|
665 | const end = this.spos + this.decoder.read()
|
666 | const res = this.str.slice(this.spos, end)
|
667 | this.spos = end
|
668 | return res
|
669 | }
|
670 | }
|