Trie.js 7.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143
  1. "use strict";
  2. Object.defineProperty(exports, "__esModule", { value: true });
  3. exports.Trie = exports.createTrieFromBase64 = exports.UTRIE2_INDEX_2_MASK = exports.UTRIE2_INDEX_2_BLOCK_LENGTH = exports.UTRIE2_OMITTED_BMP_INDEX_1_LENGTH = exports.UTRIE2_INDEX_1_OFFSET = exports.UTRIE2_UTF8_2B_INDEX_2_LENGTH = exports.UTRIE2_UTF8_2B_INDEX_2_OFFSET = exports.UTRIE2_INDEX_2_BMP_LENGTH = exports.UTRIE2_LSCP_INDEX_2_LENGTH = exports.UTRIE2_DATA_MASK = exports.UTRIE2_DATA_BLOCK_LENGTH = exports.UTRIE2_LSCP_INDEX_2_OFFSET = exports.UTRIE2_SHIFT_1_2 = exports.UTRIE2_INDEX_SHIFT = exports.UTRIE2_SHIFT_1 = exports.UTRIE2_SHIFT_2 = void 0;
  4. var Util_1 = require("./Util");
  5. /** Shift size for getting the index-2 table offset. */
  6. exports.UTRIE2_SHIFT_2 = 5;
  7. /** Shift size for getting the index-1 table offset. */
  8. exports.UTRIE2_SHIFT_1 = 6 + 5;
  9. /**
  10. * Shift size for shifting left the index array values.
  11. * Increases possible data size with 16-bit index values at the cost
  12. * of compactability.
  13. * This requires data blocks to be aligned by UTRIE2_DATA_GRANULARITY.
  14. */
  15. exports.UTRIE2_INDEX_SHIFT = 2;
  16. /**
  17. * Difference between the two shift sizes,
  18. * for getting an index-1 offset from an index-2 offset. 6=11-5
  19. */
  20. exports.UTRIE2_SHIFT_1_2 = exports.UTRIE2_SHIFT_1 - exports.UTRIE2_SHIFT_2;
  21. /**
  22. * The part of the index-2 table for U+D800..U+DBFF stores values for
  23. * lead surrogate code _units_ not code _points_.
  24. * Values for lead surrogate code _points_ are indexed with this portion of the table.
  25. * Length=32=0x20=0x400>>UTRIE2_SHIFT_2. (There are 1024=0x400 lead surrogates.)
  26. */
  27. exports.UTRIE2_LSCP_INDEX_2_OFFSET = 0x10000 >> exports.UTRIE2_SHIFT_2;
  28. /** Number of entries in a data block. 32=0x20 */
  29. exports.UTRIE2_DATA_BLOCK_LENGTH = 1 << exports.UTRIE2_SHIFT_2;
  30. /** Mask for getting the lower bits for the in-data-block offset. */
  31. exports.UTRIE2_DATA_MASK = exports.UTRIE2_DATA_BLOCK_LENGTH - 1;
  32. exports.UTRIE2_LSCP_INDEX_2_LENGTH = 0x400 >> exports.UTRIE2_SHIFT_2;
  33. /** Count the lengths of both BMP pieces. 2080=0x820 */
  34. exports.UTRIE2_INDEX_2_BMP_LENGTH = exports.UTRIE2_LSCP_INDEX_2_OFFSET + exports.UTRIE2_LSCP_INDEX_2_LENGTH;
  35. /**
  36. * The 2-byte UTF-8 version of the index-2 table follows at offset 2080=0x820.
  37. * Length 32=0x20 for lead bytes C0..DF, regardless of UTRIE2_SHIFT_2.
  38. */
  39. exports.UTRIE2_UTF8_2B_INDEX_2_OFFSET = exports.UTRIE2_INDEX_2_BMP_LENGTH;
  40. exports.UTRIE2_UTF8_2B_INDEX_2_LENGTH = 0x800 >> 6; /* U+0800 is the first code point after 2-byte UTF-8 */
  41. /**
  42. * The index-1 table, only used for supplementary code points, at offset 2112=0x840.
  43. * Variable length, for code points up to highStart, where the last single-value range starts.
  44. * Maximum length 512=0x200=0x100000>>UTRIE2_SHIFT_1.
  45. * (For 0x100000 supplementary code points U+10000..U+10ffff.)
  46. *
  47. * The part of the index-2 table for supplementary code points starts
  48. * after this index-1 table.
  49. *
  50. * Both the index-1 table and the following part of the index-2 table
  51. * are omitted completely if there is only BMP data.
  52. */
  53. exports.UTRIE2_INDEX_1_OFFSET = exports.UTRIE2_UTF8_2B_INDEX_2_OFFSET + exports.UTRIE2_UTF8_2B_INDEX_2_LENGTH;
  54. /**
  55. * Number of index-1 entries for the BMP. 32=0x20
  56. * This part of the index-1 table is omitted from the serialized form.
  57. */
  58. exports.UTRIE2_OMITTED_BMP_INDEX_1_LENGTH = 0x10000 >> exports.UTRIE2_SHIFT_1;
  59. /** Number of entries in an index-2 block. 64=0x40 */
  60. exports.UTRIE2_INDEX_2_BLOCK_LENGTH = 1 << exports.UTRIE2_SHIFT_1_2;
  61. /** Mask for getting the lower bits for the in-index-2-block offset. */
  62. exports.UTRIE2_INDEX_2_MASK = exports.UTRIE2_INDEX_2_BLOCK_LENGTH - 1;
  63. var slice16 = function (view, start, end) {
  64. if (view.slice) {
  65. return view.slice(start, end);
  66. }
  67. return new Uint16Array(Array.prototype.slice.call(view, start, end));
  68. };
  69. var slice32 = function (view, start, end) {
  70. if (view.slice) {
  71. return view.slice(start, end);
  72. }
  73. return new Uint32Array(Array.prototype.slice.call(view, start, end));
  74. };
  75. var createTrieFromBase64 = function (base64, _byteLength) {
  76. var buffer = Util_1.decode(base64);
  77. var view32 = Array.isArray(buffer) ? Util_1.polyUint32Array(buffer) : new Uint32Array(buffer);
  78. var view16 = Array.isArray(buffer) ? Util_1.polyUint16Array(buffer) : new Uint16Array(buffer);
  79. var headerLength = 24;
  80. var index = slice16(view16, headerLength / 2, view32[4] / 2);
  81. var data = view32[5] === 2
  82. ? slice16(view16, (headerLength + view32[4]) / 2)
  83. : slice32(view32, Math.ceil((headerLength + view32[4]) / 4));
  84. return new Trie(view32[0], view32[1], view32[2], view32[3], index, data);
  85. };
  86. exports.createTrieFromBase64 = createTrieFromBase64;
  87. var Trie = /** @class */ (function () {
  88. function Trie(initialValue, errorValue, highStart, highValueIndex, index, data) {
  89. this.initialValue = initialValue;
  90. this.errorValue = errorValue;
  91. this.highStart = highStart;
  92. this.highValueIndex = highValueIndex;
  93. this.index = index;
  94. this.data = data;
  95. }
  96. /**
  97. * Get the value for a code point as stored in the Trie.
  98. *
  99. * @param codePoint the code point
  100. * @return the value
  101. */
  102. Trie.prototype.get = function (codePoint) {
  103. var ix;
  104. if (codePoint >= 0) {
  105. if (codePoint < 0x0d800 || (codePoint > 0x0dbff && codePoint <= 0x0ffff)) {
  106. // Ordinary BMP code point, excluding leading surrogates.
  107. // BMP uses a single level lookup. BMP index starts at offset 0 in the Trie2 index.
  108. // 16 bit data is stored in the index array itself.
  109. ix = this.index[codePoint >> exports.UTRIE2_SHIFT_2];
  110. ix = (ix << exports.UTRIE2_INDEX_SHIFT) + (codePoint & exports.UTRIE2_DATA_MASK);
  111. return this.data[ix];
  112. }
  113. if (codePoint <= 0xffff) {
  114. // Lead Surrogate Code Point. A Separate index section is stored for
  115. // lead surrogate code units and code points.
  116. // The main index has the code unit data.
  117. // For this function, we need the code point data.
  118. // Note: this expression could be refactored for slightly improved efficiency, but
  119. // surrogate code points will be so rare in practice that it's not worth it.
  120. ix = this.index[exports.UTRIE2_LSCP_INDEX_2_OFFSET + ((codePoint - 0xd800) >> exports.UTRIE2_SHIFT_2)];
  121. ix = (ix << exports.UTRIE2_INDEX_SHIFT) + (codePoint & exports.UTRIE2_DATA_MASK);
  122. return this.data[ix];
  123. }
  124. if (codePoint < this.highStart) {
  125. // Supplemental code point, use two-level lookup.
  126. ix = exports.UTRIE2_INDEX_1_OFFSET - exports.UTRIE2_OMITTED_BMP_INDEX_1_LENGTH + (codePoint >> exports.UTRIE2_SHIFT_1);
  127. ix = this.index[ix];
  128. ix += (codePoint >> exports.UTRIE2_SHIFT_2) & exports.UTRIE2_INDEX_2_MASK;
  129. ix = this.index[ix];
  130. ix = (ix << exports.UTRIE2_INDEX_SHIFT) + (codePoint & exports.UTRIE2_DATA_MASK);
  131. return this.data[ix];
  132. }
  133. if (codePoint <= 0x10ffff) {
  134. return this.data[this.highValueIndex];
  135. }
  136. }
  137. // Fall through. The code point is outside of the legal range of 0..0x10ffff.
  138. return this.errorValue;
  139. };
  140. return Trie;
  141. }());
  142. exports.Trie = Trie;
  143. //# sourceMappingURL=Trie.js.map