https://noman-ai.jp/assets/lib0--encoding-166930f5.js

1/**
2 * Efficient schema-less binary encoding with support for variable length encoding.
3 *
4 * Use [lib0/encoding] with [lib0/decoding]. 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 = 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 = 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 encoding
27 */
28
29import * as math from 'lib0/math'
30import * as number from 'lib0/number'
31import * as binary from 'lib0/binary'
32import * as string from 'lib0/string'
33import * as array from 'lib0/array'
34
35/**
36 * A BinaryEncoder handles the encoding to an Uint8Array.
37 */
38export class Encoder {
39  constructor () {
40    this.cpos = 0
41    this.cbuf = new Uint8Array(100)
42    /**
43     * @type {Array<Uint8Array>}
44     */
45    this.bufs = []
46  }
47}
48
49/**
50 * @function
51 * @return {Encoder}
52 */
53export const createEncoder = () => new Encoder()
54
55/**
56 * @param {function(Encoder):void} f
57 */
58export const encode = (f) => {
59  const encoder = createEncoder()
60  f(encoder)
61  return toUint8Array(encoder)
62}
63
64/**
65 * The current length of the encoded data.
66 *
67 * @function
68 * @param {Encoder} encoder
69 * @return {number}
70 */
71export const length = encoder => {
72  let len = encoder.cpos
73  for (let i = 0; i < encoder.bufs.length; i++) {
74    len += encoder.bufs[i].length
75  }
76  return len
77}
78
79/**
80 * Check whether encoder is empty.
81 *
82 * @function
83 * @param {Encoder} encoder
84 * @return {boolean}
85 */
86export const hasContent = encoder => encoder.cpos > 0 || encoder.bufs.length > 0
87
88/**
89 * Transform to Uint8Array.
90 *
91 * @function
92 * @param {Encoder} encoder
93 * @return {Uint8Array} The created ArrayBuffer.
94 */
95export const toUint8Array = encoder => {
96  const uint8arr = new Uint8Array(length(encoder))
97  let curPos = 0
98  for (let i = 0; i < encoder.bufs.length; i++) {
99    const d = encoder.bufs[i]
100    uint8arr.set(d, curPos)
101    curPos += d.length
102  }
103  uint8arr.set(new Uint8Array(encoder.cbuf.buffer, 0, encoder.cpos), curPos)
104  return uint8arr
105}
106
107/**
108 * Verify that it is possible to write `len` bytes wtihout checking. If
109 * necessary, a new Buffer with the required length is attached.
110 *
111 * @param {Encoder} encoder
112 * @param {number} len
113 */
114export const verifyLen = (encoder, len) => {
115  const bufferLen = encoder.cbuf.length
116  if (bufferLen - encoder.cpos < len) {
117    encoder.bufs.push(new Uint8Array(encoder.cbuf.buffer, 0, encoder.cpos))
118    encoder.cbuf = new Uint8Array(math.max(bufferLen, len) * 2)
119    encoder.cpos = 0
120  }
121}
122
123/**
124 * Write one byte to the encoder.
125 *
126 * @function
127 * @param {Encoder} encoder
128 * @param {number} num The byte that is to be encoded.
129 */
130export const write = (encoder, num) => {
131  const bufferLen = encoder.cbuf.length
132  if (encoder.cpos === bufferLen) {
133    encoder.bufs.push(encoder.cbuf)
134    encoder.cbuf = new Uint8Array(bufferLen * 2)
135    encoder.cpos = 0
136  }
137  encoder.cbuf[encoder.cpos++] = num
138}
139
140/**
141 * Write one byte at a specific position.
142 * Position must already be written (i.e. encoder.length > pos)
143 *
144 * @function
145 * @param {Encoder} encoder
146 * @param {number} pos Position to which to write data
147 * @param {number} num Unsigned 8-bit integer
148 */
149export const set = (encoder, pos, num) => {
150  let buffer = null
151  // iterate all buffers and adjust position
152  for (let i = 0; i < encoder.bufs.length && buffer === null; i++) {
153    const b = encoder.bufs[i]
154    if (pos < b.length) {
155      buffer = b // found buffer
156    } else {
157      pos -= b.length
158    }
159  }
160  if (buffer === null) {
161    // use current buffer
162    buffer = encoder.cbuf
163  }
164  buffer[pos] = num
165}
166
167/**
168 * Write one byte as an unsigned integer.
169 *
170 * @function
171 * @param {Encoder} encoder
172 * @param {number} num The number that is to be encoded.
173 */
174export const writeUint8 = write
175
176/**
177 * Write one byte as an unsigned Integer at a specific location.
178 *
179 * @function
180 * @param {Encoder} encoder
181 * @param {number} pos The location where the data will be written.
182 * @param {number} num The number that is to be encoded.
183 */
184export const setUint8 = set
185
186/**
187 * Write two bytes as an unsigned integer.
188 *
189 * @function
190 * @param {Encoder} encoder
191 * @param {number} num The number that is to be encoded.
192 */
193export const writeUint16 = (encoder, num) => {
194  write(encoder, num & binary.BITS8)
195  write(encoder, (num >>> 8) & binary.BITS8)
196}
197/**
198 * Write two bytes as an unsigned integer at a specific location.
199 *
200 * @function
201 * @param {Encoder} encoder
202 * @param {number} pos The location where the data will be written.
203 * @param {number} num The number that is to be encoded.
204 */
205export const setUint16 = (encoder, pos, num) => {
206  set(encoder, pos, num & binary.BITS8)
207  set(encoder, pos + 1, (num >>> 8) & binary.BITS8)
208}
209
210/**
211 * Write two bytes as an unsigned integer
212 *
213 * @function
214 * @param {Encoder} encoder
215 * @param {number} num The number that is to be encoded.
216 */
217export const writeUint32 = (encoder, num) => {
218  for (let i = 0; i < 4; i++) {
219    write(encoder, num & binary.BITS8)
220    num >>>= 8
221  }
222}
223
224/**
225 * Write two bytes as an unsigned integer in big endian order.
226 * (most significant byte first)
227 *
228 * @function
229 * @param {Encoder} encoder
230 * @param {number} num The number that is to be encoded.
231 */
232export const writeUint32BigEndian = (encoder, num) => {
233  for (let i = 3; i >= 0; i--) {
234    write(encoder, (num >>> (8 * i)) & binary.BITS8)
235  }
236}
237
238/**
239 * Write two bytes as an unsigned integer at a specific location.
240 *
241 * @function
242 * @param {Encoder} encoder
243 * @param {number} pos The location where the data will be written.
244 * @param {number} num The number that is to be encoded.
245 */
246export const setUint32 = (encoder, pos, num) => {
247  for (let i = 0; i < 4; i++) {
248    set(encoder, pos + i, num & binary.BITS8)
249    num >>>= 8
250  }
251}
252
253/**
254 * Write a variable length unsigned integer. Max encodable integer is 2^53.
255 *
256 * @function
257 * @param {Encoder} encoder
258 * @param {number} num The number that is to be encoded.
259 */
260export const writeVarUint = (encoder, num) => {
261  while (num > binary.BITS7) {
262    write(encoder, binary.BIT8 | (binary.BITS7 & num))
263    num = math.floor(num / 128) // shift >>> 7
264  }
265  write(encoder, binary.BITS7 & num)
266}
267
268/**
269 * Write a variable length integer.
270 *
271 * We use the 7th bit instead for signaling that this is a negative number.
272 *
273 * @function
274 * @param {Encoder} encoder
275 * @param {number} num The number that is to be encoded.
276 */
277export const writeVarInt = (encoder, num) => {
278  const isNegative = math.isNegativeZero(num)
279  if (isNegative) {
280    num = -num
281  }
282  //             |- whether to continue reading         |- whether is negative     |- number
283  write(encoder, (num > binary.BITS6 ? binary.BIT8 : 0) | (isNegative ? binary.BIT7 : 0) | (binary.BITS6 & num))
284  num = math.floor(num / 64) // shift >>> 6
285  // We don't need to consider the case of num === 0 so we can use a different
286  // pattern here than above.
287  while (num > 0) {
288    write(encoder, (num > binary.BITS7 ? binary.BIT8 : 0) | (binary.BITS7 & num))
289    num = math.floor(num / 128) // shift >>> 7
290  }
291}
292
293/**
294 * A cache to store strings temporarily
295 */
296const _strBuffer = new Uint8Array(30000)
297const _maxStrBSize = _strBuffer.length / 3
298
299/**
300 * Write a variable length string.
301 *
302 * @function
303 * @param {Encoder} encoder
304 * @param {String} str The string that is to be encoded.
305 */
306export const _writeVarStringNative = (encoder, str) => {
307  if (str.length < _maxStrBSize) {
308    // We can encode the string into the existing buffer
309    /* c8 ignore next */
310    const written = string.utf8TextEncoder.encodeInto(str, _strBuffer).written || 0
311    writeVarUint(encoder, written)
312    for (let i = 0; i < written; i++) {
313      write(encoder, _strBuffer[i])
314    }
315  } else {
316    writeVarUint8Array(encoder, string.encodeUtf8(str))
317  }
318}
319
320/**
321 * Write a variable length string.
322 *
323 * @function
324 * @param {Encoder} encoder
325 * @param {String} str The string that is to be encoded.
326 */
327export const _writeVarStringPolyfill = (encoder, str) => {
328  const encodedString = unescape(encodeURIComponent(str))
329  const len = encodedString.length
330  writeVarUint(encoder, len)
331  for (let i = 0; i < len; i++) {
332    write(encoder, /** @type {number} */ (encodedString.codePointAt(i)))
333  }
334}
335
336/**
337 * Write a variable length string.
338 *
339 * @function
340 * @param {Encoder} encoder
341 * @param {String} str The string that is to be encoded.
342 */
343/* c8 ignore next */
344export const writeVarString = (string.utf8TextEncoder && /** @type {any} */ (string.utf8TextEncoder).encodeInto) ? _writeVarStringNative : _writeVarStringPolyfill
345
346/**
347 * Write a string terminated by a special byte sequence. This is not very performant and is
348 * generally discouraged. However, the resulting byte arrays are lexiographically ordered which
349 * makes this a nice feature for databases.
350 *
351 * The string will be encoded using utf8 and then terminated and escaped using writeTerminatingUint8Array.
352 *
353 * @function
354 * @param {Encoder} encoder
355 * @param {String} str The string that is to be encoded.
356 */
357export const writeTerminatedString = (encoder, str) =>
358  writeTerminatedUint8Array(encoder, string.encodeUtf8(str))
359
360/**
361 * Write a terminating Uint8Array. Note that this is not performant and is generally
362 * discouraged. There are few situations when this is needed.
363 *
364 * We use 0x0 as a terminating character. 0x1 serves as an escape character for 0x0 and 0x1.
365 *
366 * Example: [0,1,2] is encoded to [1,0,1,1,2,0]. 0x0, and 0x1 needed to be escaped using 0x1. Then
367 * the result is terminated using the 0x0 character.
368 *
369 * This is basically how many systems implement null terminated strings. However, we use an escape
370 * character 0x1 to avoid issues and potenial attacks on our database (if this is used as a key
371 * encoder for NoSql databases).
372 *
373 * @function
374 * @param {Encoder} encoder
375 * @param {Uint8Array} buf The string that is to be encoded.
376 */
377export const writeTerminatedUint8Array = (encoder, buf) => {
378  for (let i = 0; i < buf.length; i++) {
379    const b = buf[i]
380    if (b === 0 || b === 1) {
381      write(encoder, 1)
382    }
383    write(encoder, buf[i])
384  }
385  write(encoder, 0)
386}
387
388/**
389 * Write the content of another Encoder.
390 *
391 * @TODO: can be improved!
392 *        - Note: Should consider that when appending a lot of small Encoders, we should rather clone than referencing the old structure.
393 *                Encoders start with a rather big initial buffer.
394 *
395 * @function
396 * @param {Encoder} encoder The enUint8Arr
397 * @param {Encoder} append The BinaryEncoder to be written.
398 */
399export const writeBinaryEncoder = (encoder, append) => writeUint8Array(encoder, toUint8Array(append))
400
401/**
402 * Append fixed-length Uint8Array to the encoder.
403 *
404 * @function
405 * @param {Encoder} encoder
406 * @param {Uint8Array} uint8Array
407 */
408export const writeUint8Array = (encoder, uint8Array) => {
409  const bufferLen = encoder.cbuf.length
410  const cpos = encoder.cpos
411  const leftCopyLen = math.min(bufferLen - cpos, uint8Array.length)
412  const rightCopyLen = uint8Array.length - leftCopyLen
413  encoder.cbuf.set(uint8Array.subarray(0, leftCopyLen), cpos)
414  encoder.cpos += leftCopyLen
415  if (rightCopyLen > 0) {
416    // Still something to write, write right half..
417    // Append new buffer
418    encoder.bufs.push(encoder.cbuf)
419    // must have at least size of remaining buffer
420    encoder.cbuf = new Uint8Array(math.max(bufferLen * 2, rightCopyLen))
421    // copy array
422    encoder.cbuf.set(uint8Array.subarray(leftCopyLen))
423    encoder.cpos = rightCopyLen
424  }
425}
426
427/**
428 * Append an Uint8Array to Encoder.
429 *
430 * @function
431 * @param {Encoder} encoder
432 * @param {Uint8Array} uint8Array
433 */
434export const writeVarUint8Array = (encoder, uint8Array) => {
435  writeVarUint(encoder, uint8Array.byteLength)
436  writeUint8Array(encoder, uint8Array)
437}
438
439/**
440 * Create an DataView of the next `len` bytes. Use it to write data after
441 * calling this function.
442 *
443 * ```js
444 * // write float32 using DataView
445 * const dv = writeOnDataView(encoder, 4)
446 * dv.setFloat32(0, 1.1)
447 * // read float32 using DataView
448 * const dv = readFromDataView(encoder, 4)
449 * dv.getFloat32(0) // => 1.100000023841858 (leaving it to the reader to find out why this is the correct result)
450 * ```
451 *
452 * @param {Encoder} encoder
453 * @param {number} len
454 * @return {DataView}
455 */
456export const writeOnDataView = (encoder, len) => {
457  verifyLen(encoder, len)
458  const dview = new DataView(encoder.cbuf.buffer, encoder.cpos, len)
459  encoder.cpos += len
460  return dview
461}
462
463/**
464 * @param {Encoder} encoder
465 * @param {number} num
466 */
467export const writeFloat32 = (encoder, num) => writeOnDataView(encoder, 4).setFloat32(0, num, false)
468
469/**
470 * @param {Encoder} encoder
471 * @param {number} num
472 */
473export const writeFloat64 = (encoder, num) => writeOnDataView(encoder, 8).setFloat64(0, num, false)
474
475/**
476 * @param {Encoder} encoder
477 * @param {bigint} num
478 */
479export const writeBigInt64 = (encoder, num) => /** @type {any} */ (writeOnDataView(encoder, 8)).setBigInt64(0, num, false)
480
481/**
482 * @param {Encoder} encoder
483 * @param {bigint} num
484 */
485export const writeBigUint64 = (encoder, num) => /** @type {any} */ (writeOnDataView(encoder, 8)).setBigUint64(0, num, false)
486
487const floatTestBed = new DataView(new ArrayBuffer(4))
488/**
489 * Check if a number can be encoded as a 32 bit float.
490 *
491 * @param {number} num
492 * @return {boolean}
493 */
494const isFloat32 = num => {
495  floatTestBed.setFloat32(0, num)
496  return floatTestBed.getFloat32(0) === num
497}
498
499/**
500 * Encode data with efficient binary format.
501 *
502 * Differences to JSON:
503 * • Transforms data to a binary format (not to a string)
504 * • Encodes undefined, NaN, and ArrayBuffer (these can't be represented in JSON)
505 * • Numbers are efficiently encoded either as a variable length integer, as a
506 *   32 bit float, as a 64 bit float, or as a 64 bit bigint.
507 *
508 * Encoding table:
509 *
510 * | Data Type           | Prefix   | Encoding Method    | Comment |
511 * | ------------------- | -------- | ------------------ | ------- |
512 * | undefined           | 127      |                    | Functions, symbol, and everything that cannot be identified is encoded as undefined |
513 * | null                | 126      |                    | |
514 * | integer             | 125      | writeVarInt        | Only encodes 32 bit signed integers |
515 * | float32             | 124      | writeFloat32       | |
516 * | float64             | 123      | writeFloat64       | |
517 * | bigint              | 122      | writeBigInt64      | |
518 * | boolean (false)     | 121      |                    | True and false are different data types so we save the following byte |
519 * | boolean (true)      | 120      |                    | - 0b01111000 so the last bit determines whether true or false |
520 * | string              | 119      | writeVarString     | |
521 * | object<string,any>  | 118      | custom             | Writes {length} then {length} key-value pairs |
522 * | array<any>          | 117      | custom             | Writes {length} then {length} json values |
523 * | Uint8Array          | 116      | writeVarUint8Array | We use Uint8Array for any kind of binary data |
524 *
525 * Reasons for the decreasing prefix:
526 * We need the first bit for extendability (later we may want to encode the
527 * prefix with writeVarUint). The remaining 7 bits are divided as follows:
528 * [0-30]   the beginning of the data range is used for custom purposes
529 *          (defined by the function that uses this library)
530 * [31-127] the end of the data range is used for data encoding by
531 *          lib0/encoding.js
532 *
533 * @param {Encoder} encoder
534 * @param {undefined|null|number|bigint|boolean|string|Object<string,any>|Array<any>|Uint8Array

534} data
535 */
536export const writeAny = (encoder, data) => {
537  switch (typeof data) {
538    case 'string':
539      // TYPE 119: STRING
540      write(encoder, 119)
541      writeVarString(encoder, data)
542      break
543    case 'number':
544      if (number.isInteger(data) && math.abs(data) <= binary.BITS31) {
545        // TYPE 125: INTEGER
546        write(encoder, 125)
547        writeVarInt(encoder, data)
548      } else if (isFloat32(data)) {
549        // TYPE 124: FLOAT32
550        write(encoder, 124)
551        writeFloat32(encoder, data)
552      } else {
553        // TYPE 123: FLOAT64
554        write(encoder, 123)
555        writeFloat64(encoder, data)
556      }
557      break
558    case 'bigint':
559      // TYPE 122: BigInt
560      write(encoder, 122)
561      writeBigInt64(encoder, data)
562      break
563    case 'object':
564      if (data === null) {
565        // TYPE 126: null
566        write(encoder, 126)
567      } else if (array.isArray(data)) {
568        // TYPE 117: Array
569        write(encoder, 117)
570        writeVarUint(encoder, data.length)
571        for (let i = 0; i < data.length; i++) {
572          writeAny(encoder, data[i])
573        }
574      } else if (data instanceof Uint8Array) {
575        // TYPE 116: ArrayBuffer
576        write(encoder, 116)
577        writeVarUint8Array(encoder, data)
578      } else {
579        // TYPE 118: Object
580        write(encoder, 118)
581        const keys = Object.keys(data)
582        writeVarUint(encoder, keys.length)
583        for (let i = 0; i < keys.length; i++) {
584          const key = keys[i]
585          writeVarString(encoder, key)
586          writeAny(encoder, data[key])
587        }
588      }
589      break
590    case 'boolean':
591      // TYPE 120/121: boolean (true/false)
592      write(encoder, data ? 120 : 121)
593      break
594    default:
595      // TYPE 127: undefined
596      write(encoder, 127)
597  }
598}
599
600/**
601 * Now come a few stateful encoder that have their own classes.
602 */
603
604/**
605 * Basic Run Length Encoder - a basic compression implementation.
606 *
607 * Encodes [1,1,1,7] to [1,3,7,1] (3 times 1, 1 time 7). This encoder might do more harm than good if there are a lot of values that are not repeated.
608 *
609 * It was originally used for image compression. Cool .. article http://csbruce.com/cbm/transactor/pdfs/trans_v7_i06.pdf
610 *
611 * @note T must not be null!
612 *
613 * @template T
614 */
615export class RleEncoder extends Encoder {
616  /**
617   * @param {function(Encoder, T):void} writer
618   */
619  constructor (writer) {
620    super()
621    /**
622     * The writer
623     */
624    this.w = writer
625    /**
626     * Current state
627     * @type {T|null}
628     */
629    this.s = null
630    this.count = 0
631  }
632
633  /**
634   * @param {T} v
635   */
636  write (v) {
637    if (this.s === v) {
638      this.count++
639    } else {
640      if (this.count > 0) {
641        // flush counter, unless this is the first value (count = 0)
642        writeVarUint(this, this.count - 1) // since count is always > 0, we can decrement by one. non-standard encoding ftw
643      }
644      this.count = 1
645      // write first value
646      this.w(this, v)
647      this.s = v
648    }
649  }
650}
651
652/**
653 * Basic diff decoder using variable length encoding.
654 *
655 * Encodes the values [3, 1100, 1101, 1050, 0] to [3, 1097, 1, -51, -1050] using writeVarInt.
656 */
657export class IntDiffEncoder extends Encoder {
658  /**
659   * @param {number} start
660   */
661  constructor (start) {
662    super()
663    /**
664     * Current state
665     * @type {number}
666     */
667    this.s = start
668  }
669
670  /**
671   * @param {number} v
672   */
673  write (v) {
674    writeVarInt(this, v - this.s)
675    this.s = v
676  }
677}
678
679/**
680 * A combination of IntDiffEncoder and RleEncoder.
681 *
682 * Basically first writes the IntDiffEncoder and then counts duplicate diffs using RleEncoding.
683 *
684 * Encodes the values [1,1,1,2,3,4,5,6] as [1,1,0,2,1,5] (RLE([1,0,0,1,1,1,1,1]) ⇒ RleIntDiff[1,1,0,2,1,5])
685 */
686export class RleIntDiffEncoder extends Encoder {
687  /**
688   * @param {number} start
689   */
690  constructor (start) {
691    super()
692    /**
693     * Current state
694     * @type {number}
695     */
696    this.s = start
697    this.count = 0
698  }
699
700  /**
701   * @param {number} v
702   */
703  write (v) {
704    if (this.s === v && this.count > 0) {
705      this.count++
706    } else {
707      if (this.count > 0) {
708        // flush counter, unless this is the first value (count = 0)
709        writeVarUint(this, this.count - 1) // since count is always > 0, we can decrement by one. non-standard encoding ftw
710      }
711      this.count = 1
712      // write first value
713      writeVarInt(this, v - this.s)
714      this.s = v
715    }
716  }
717}
718
719/**
720 * @param {UintOptRleEncoder} encoder
721 */
722const flushUintOptRleEncoder = encoder => {
723  if (encoder.count > 0) {
724    // flush counter, unless this is the first value (count = 0)
725    // case 1: just a single value. set sign to positive
726    // case 2: write several values. set sign to negative to indicate that there is a length coming
727    writeVarInt(encoder.encoder, encoder.count === 1 ? encoder.s : -encoder.s)
728    if (encoder.count > 1) {
729      writeVarUint(encoder.encoder, encoder.count - 2) // since count is always > 1, we can decrement by one. non-standard encoding ftw
730    }
731  }
732}
733
734/**
735 * Optimized Rle encoder that does not suffer from the mentioned problem of the basic Rle encoder.
736 *
737 * Internally uses VarInt encoder to write unsigned integers. If the input occurs multiple times, we write
738 * write it as a negative number. The UintOptRleDecoder then understands that it needs to read a count.
739 *
740 * Encodes [1,2,3,3,3] as [1,2,-3,3] (once 1, once 2, three times 3)
741 */
742export class UintOptRleEncoder {
743  constructor () {
744    this.encoder = new Encoder()
745    /**
746     * @type {number}
747     */
748    this.s = 0
749    this.count = 0
750  }
751
752  /**
753   * @param {number} v
754   */
755  write (v) {
756    if (this.s === v) {
757      this.count++
758    } else {
759      flushUintOptRleEncoder(this)
760      this.count = 1
761      this.s = v
762    }
763  }
764
765  /**
766   * Flush the encoded state and transform this to a Uint8Array.
767   *
768   * Note that this should only be called once.
769   */
770  toUint8Array () {
771    flushUintOptRleEncoder(this)
772    return toUint8Array(this.encoder)
773  }
774}
775
776/**
777 * Increasing Uint Optimized RLE Encoder
778 *
779 * The RLE encoder counts the number of same occurences of the same value.
780 * The IncUintOptRle encoder counts if the value increases.
781 * I.e. 7, 8, 9, 10 will be encoded as [-7, 4]. 1, 3, 5 will be encoded
782 * as [1, 3, 5].
783 */
784export class IncUintOptRleEncoder {
785  constructor () {
786    this.encoder = new Encoder()
787    /**
788     * @type {number}
789     */
790    this.s = 0
791    this.count = 0
792  }
793
794  /**
795   * @param {number} v
796   */
797  write (v) {
798    if (this.s + this.count === v) {
799      this.count++
800    } else {
801      flushUintOptRleEncoder(this)
802      this.count = 1
803      this.s = v
804    }
805  }
806
807  /**
808   * Flush the encoded state and transform this to a Uint8Array.
809   *
810   * Note that this should only be called once.
811   */
812  toUint8Array () {
813    flushUintOptRleEncoder(this)
814    return toUint8Array(this.encoder)
815  }
816}
817
818/**
819 * @param {IntDiffOptRleEncoder} encoder
820 */
821const flushIntDiffOptRleEncoder = encoder => {
822  if (encoder.count > 0) {
823    //          31 bit making up the diff | wether to write the counter
824    // const encodedDiff = encoder.diff << 1 | (encoder.count === 1 ? 0 : 1)
825    const encodedDiff = encoder.diff * 2 + (encoder.count === 1 ? 0 : 1)
826    // flush counter, unless this is the first value (count = 0)
827    // case 1: just a single value. set first bit to positive
828    // case 2: write several values. set first bit to negative to indicate that there is a length coming
829    writeVarInt(encoder.encoder, encodedDiff)
830    if (encoder.count > 1) {
831      writeVarUint(encoder.encoder, encoder.count - 2) // since count is always > 1, we can decrement by one. non-standard encoding ftw
832    }
833  }
834}
835
836/**
837 * A combination of the IntDiffEncoder and the UintOptRleEncoder.
838 *
839 * The count approach is similar to the UintDiffOptRleEncoder, but instead of using the negative bitflag, it encodes
840 * in the LSB whether a count is to be read. Therefore this Encoder only supports 31 bit integers!
841 *
842 * Encodes [1, 2, 3, 2] as [3, 1, 6, -1] (more specifically [(1 << 1) | 1, (3 << 0) | 0, -1])
843 *
844 * Internally uses variable length encoding. Contrary to normal UintVar encoding, the first byte contains:
845 * * 1 bit that denotes whether the next value is a count (LSB)
846 * * 1 bit that denotes whether this value is negative (MSB - 1)
847 * * 1 bit that denotes whether to continue reading the variable length integer (MSB)
848 *
849 * Therefore, only five bits remain to encode diff ranges.
850 *
851 * Use this Encoder only when appropriate. In most cases, this is probably a bad idea.
852 */
853export class IntDiffOptRleEncoder {
854  constructor () {
855    this.encoder = new Encoder()
856    /**
857     * @type {number}
858     */
859    this.s = 0
860    this.count = 0
861    this.diff = 0
862  }
863
864  /**
865   * @param {number} v
866   */
867  write (v) {
868    if (this.diff === v - this.s) {
869      this.s = v
870      this.count++
871    } else {
872      flushIntDiffOptRleEncoder(this)
873      this.count = 1
874      this.diff = v - this.s
875      this.s = v
876    }
877  }
878
879  /**
880   * Flush the encoded state and transform this to a Uint8Array.
881   *
882   * Note that this should only be called once.
883   */
884  toUint8Array () {
885    flushIntDiffOptRleEncoder(this)
886    return toUint8Array(this.encoder)
887  }
888}
889
890/**
891 * Optimized String Encoder.
892 *
893 * Encoding many small strings in a simple Encoder is not very efficient. The function call to decode a string takes some time and creates references that must be eventually deleted.
894 * In practice, when decoding several million small strings, the GC will kick in more and more often to collect orphaned string objects (or maybe there is another reason?).
895 *
896 * This string encoder solves the above problem. All strings are concatenated and written as a single string using a single encoding call.
897 *
898 * The lengths are encoded using a UintOptRleEncoder.
899 */
900export class StringEncoder {
901  constructor () {
902    /**
903     * @type {Array<string>}
904     */
905    this.sarr = []
906    this.s = ''
907    this.lensE = new UintOptRleEncoder()
908  }
909
910  /**
911   * @param {string} string
912   */
913  write (string) {
914    this.s += string
915    if (this.s.length > 19) {
916      this.sarr.push(this.s)
917      this.s = ''
918    }
919    this.lensE.write(string.length)
920  }
921
922  toUint8Array () {
923    const encoder = new Encoder()
924    this.sarr.push(this.s)
925    this.s = ''
926    writeVarString(encoder, this.sarr.join(''))
927    writeUint8Array(encoder, this.lensE.toUint8Array())
928    return toUint8Array(encoder)
929  }
930}