- commit
- fcee1bf186f868844bda5e46af6df52af0316956
- parent
- 61ae74fb13e7c240aa6ff84713f85e87e1faae7b
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2024-05-29 13:15
Revert "Revert "lzw compression"" This reverts commit 087fe6da8a9a0eb918837c5a106871c0218059cc.
Diffstat
| A | static/lzw.js | 128 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | static/main.js | 5 | +++-- |
2 files changed, 131 insertions, 2 deletions
diff --git a/static/lzw.js b/static/lzw.js
@@ -0,0 +1,128 @@
-1 1 class Buffer {
-1 2 constructor(bytes) {
-1 3 this.bytes = bytes;
-1 4 this.i_byte = 0;
-1 5 this.i_bit = 0;
-1 6 }
-1 7
-1 8 next() {
-1 9 if (this.i_bit < 7) {
-1 10 this.i_bit += 1;
-1 11 } else {
-1 12 this.i_byte += 1;
-1 13 this.i_bit = 0;
-1 14 }
-1 15 }
-1 16
-1 17 read(size) {
-1 18 var bits = 0;
-1 19 for (let i = 0; i < size; i++) {
-1 20 if (this.bytes.length <= this.i_byte) {
-1 21 throw new RangeError();
-1 22 }
-1 23 bits <<= 1;
-1 24 if (this.bytes[this.i_byte] & (1 << (7 - this.i_bit))) {
-1 25 bits |= 1;
-1 26 }
-1 27 this.next();
-1 28 }
-1 29 return bits;
-1 30 }
-1 31
-1 32 write(bits, size) {
-1 33 for (let i = 0; i < size; i++) {
-1 34 if (this.bytes.length <= this.i_byte) {
-1 35 this.bytes.push(0);
-1 36 }
-1 37 if (bits & (1 << (size - i - 1))) {
-1 38 this.bytes[this.i_byte] |= 1 << (7 - this.i_bit);
-1 39 }
-1 40 this.next();
-1 41 }
-1 42 }
-1 43 }
-1 44
-1 45 var sIndexOf = function(dict, value) {
-1 46 var s = value.toString();
-1 47 for (let i = 0; i < dict.length; i++) {
-1 48 if (s === dict[i].toString()) {
-1 49 return i;
-1 50 }
-1 51 }
-1 52 return -1;
-1 53 };
-1 54
-1 55 export var compress = function(bytes) {
-1 56 var result = [];
-1 57 var buf = new Buffer(result);
-1 58
-1 59 var field_size = 9;
-1 60 var dict = [];
-1 61 dict.push('end');
-1 62 for (let i = 0; i < 256; i++) {
-1 63 dict.push([i]);
-1 64 }
-1 65
-1 66 var win = [];
-1 67 var i = 0;
-1 68 while (i < bytes.length) {
-1 69 var tmp = [...win, bytes[i]];
-1 70 if (sIndexOf(dict, tmp) === -1) {
-1 71 buf.write(sIndexOf(dict, win), field_size);
-1 72 win = [];
-1 73 if (dict.length >> field_size) {
-1 74 field_size += 1;
-1 75 }
-1 76 dict.push(tmp);
-1 77 } else {
-1 78 win = tmp;
-1 79 i += 1;
-1 80 }
-1 81 }
-1 82 buf.write(sIndexOf(dict, win), field_size);
-1 83 buf.write(sIndexOf(dict, 'end'), field_size);
-1 84
-1 85 return new Uint8Array(result);
-1 86 };
-1 87
-1 88 export var decompress = function(bytes) {
-1 89 var result = [];
-1 90 var buf = new Buffer(bytes);
-1 91 var prev = null;
-1 92
-1 93 var field_size = 9;
-1 94 var dict = [];
-1 95 dict.push('end');
-1 96 for (let i = 0; i < 256; i++) {
-1 97 dict.push([i]);
-1 98 }
-1 99
-1 100 while (true) {
-1 101 var index = buf.read(field_size);
-1 102 var value = dict[index];
-1 103 if (dict.length >> field_size) {
-1 104 field_size += 1;
-1 105 }
-1 106
-1 107 if (value === 'end') {
-1 108 break;
-1 109 }
-1 110
-1 111 // push to dict with one cycle delay because we need the first
-1 112 // item from the next entry.
-1 113 //
-1 114 // If value is undefined, the next entry is the not-yet-pushed one.
-1 115 // Fortunately, we know that its first item is the same as in the entry
-1 116 // before that.
-1 117 if (!value) {
-1 118 value = [...prev, prev[0]];
-1 119 }
-1 120 result = result.concat(value);
-1 121 if (prev) {
-1 122 dict.push([...prev, value[0]]);
-1 123 }
-1 124 prev = value;
-1 125 }
-1 126
-1 127 return new Uint8Array(result);
-1 128 };
diff --git a/static/main.js b/static/main.js
@@ -1,14 +1,15 @@ 1 1 import * as base64 from './base64.js'; -1 2 import * as lzw from './lzw.js'; 2 3 3 4 var encode = function(text) { 4 5 var encoder = new TextEncoder(); 5 6 var bytes = encoder.encode(text);6 -1 return base64.encode(bytes);-1 7 return base64.encode(lzw.compress(bytes)); 7 8 }; 8 9 9 10 var decode = function(string) { 10 11 var decoder = new TextDecoder();11 -1 var bytes = base64.decode(string);-1 12 var bytes = lzw.decompress(base64.decode(string)); 12 13 return decoder.decode(bytes); 13 14 }; 14 15