From b485aab7e71c1625cfc27e0f92c9509f42378458 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 5 May 2024 13:19:16 +0200 Subject: Adding upstream version 1.45.3+dfsg. Signed-off-by: Daniel Baumann --- .../h2o/libh2o/misc/oktavia/src/bit-vector.jsx | 295 --------------------- 1 file changed, 295 deletions(-) delete mode 100644 web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx (limited to 'web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx') diff --git a/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx b/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx deleted file mode 100644 index b366e43a0..000000000 --- a/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx +++ /dev/null @@ -1,295 +0,0 @@ -/** - * This is a JSX version of shellinford library: - * https://code.google.com/p/shellinford/ - * - * License: http://shibu.mit-license.org/ - */ - -import "binary-util.jsx"; - -class BitVector -{ - static const SMALL_BLOCK_SIZE : int = 32; - static const LARGE_BLOCK_SIZE : int = 256; - static const BLOCK_RATE : int = 8; - - var _v : number[]; - var _r : number[]; - var _size : int; - var _size1 : int; - - function constructor () - { - this._r = [] : number[]; - this._v = [] : number[]; - this.clear(); - } - - function build () : void - { - this._size1 = 0; - for (var i = 0; i < this._v.length; i++) - { - if (i % BitVector.BLOCK_RATE == 0) - { - this._r.push(this.size(true)); - } - this._size1 += this._rank32(this._v[i], BitVector.SMALL_BLOCK_SIZE, true); - } - } - - function clear () : void - { - this._v.length = 0; - this._r.length = 0; - this._size = 0; - this._size1 = 0; - } - - function size () : int - { - return this._size; - } - - function size (b : boolean) : int - { - return b ? (this._size1) : (this._size - this._size1); - } - - function set (value : int) : void - { - this.set(value, true); - } - - function set (value : int, flag : boolean) : void - { - if (value >= this.size()) - { - this._size = value + 1; - } - var q : int = value / BitVector.SMALL_BLOCK_SIZE; - var r : int = value % BitVector.SMALL_BLOCK_SIZE; - while (q >= this._v.length) - { - this._v.push(0); - } - var m : int = 0x1 << r; - if (flag) - { - this._v[q] |= m; - } - else - { - this._v[q] &= ~m; - } - } - - function get (value : int) : boolean - { - if (value >= this.size()) - { - throw new Error("BitVector.get() : range error"); - } - var q : int = value / BitVector.SMALL_BLOCK_SIZE; - var r : int = value % BitVector.SMALL_BLOCK_SIZE; - var m : int = 0x1 << r; - return (this._v[q] & m) as boolean; - } - - function rank (i : int) : int - { - return this.rank(i, true); - } - - function rank (i : int, b : boolean) : int - { - if (i > this.size()) - { - throw new Error("BitVector.rank() : range error"); - } - if (i == 0) - { - return 0; - } - i--; - var q_large : int = Math.floor(i / BitVector.LARGE_BLOCK_SIZE); - var q_small : int = Math.floor(i / BitVector.SMALL_BLOCK_SIZE); - var r : int = Math.floor(i % BitVector.SMALL_BLOCK_SIZE); - var rank : int = this._r[q_large]; - if (!b) - { - rank = q_large * BitVector.LARGE_BLOCK_SIZE - rank; - } - var begin = q_large * BitVector.BLOCK_RATE; - for (var j = begin; j < q_small; j++) - { - rank += this._rank32(this._v[j], BitVector.SMALL_BLOCK_SIZE, b); - } - rank += this._rank32(this._v[q_small], r + 1, b); - return rank; - } - - function select(i : int) : int - { - return this.select(i, true); - } - - function select(i : int, b : boolean) : int - { - if (i >= this.size(b)) - { - throw new Error("BitVector.select() : range error"); - } - - var left = 0; - var right = this._r.length; - while (left < right) - { - var pivot = Math.floor((left + right) / 2); - var rank = this._r[pivot]; - if (!b) - { - rank = pivot * BitVector.LARGE_BLOCK_SIZE - rank; - } - if (i < rank) - { - right = pivot; - } - else - { - left = pivot + 1; - } - } - right--; - - if (b) - { - i -= this._r[right]; - } - else - { - i -= right * BitVector.LARGE_BLOCK_SIZE - this._r[right]; - } - var j = right * BitVector.BLOCK_RATE; - while (1) - { - var rank = this._rank32(this._v[j], BitVector.SMALL_BLOCK_SIZE, b); - if (i < rank) - { - break; - } - j++; - i -= rank; - } - return j * BitVector.SMALL_BLOCK_SIZE + this._select32(this._v[j], i, b); - } - - function _rank32 (x : int, i : int, b : boolean) : int - { - if (!b) - { - x = ~x; - } - x <<= (BitVector.SMALL_BLOCK_SIZE - i); - x = ((x & 0xaaaaaaaa) >>> 1) - + (x & 0x55555555); - x = ((x & 0xcccccccc) >>> 2) - + (x & 0x33333333); - x = ((x & 0xf0f0f0f0) >>> 4) - + (x & 0x0f0f0f0f); - x = ((x & 0xff00ff00) >>> 8) - + (x & 0x00ff00ff); - x = ((x & 0xffff0000) >>> 16) - + (x & 0x0000ffff); - return x; - } - - function _select32(x : int, i : int, b : boolean) : int - { - if (!b) - { - x = ~x; - } - var x1 = ((x & 0xaaaaaaaa) >>> 1) - + (x & 0x55555555); - var x2 = ((x1 & 0xcccccccc) >>> 2) - + (x1 & 0x33333333); - var x3 = ((x2 & 0xf0f0f0f0) >>> 4) - + (x2 & 0x0f0f0f0f); - var x4 = ((x3 & 0xff00ff00) >>> 8) - + (x3 & 0x00ff00ff); - var x5 = ((x4 & 0xffff0000) >>> 16) - + (x4 & 0x0000ffff); - i++; - var pos = 0; - var v5 = x5 & 0xffffffff; - if (i > v5) - { - i -= v5; - pos += 32; - } - var v4 = (x4 >>> pos) & 0x0000ffff; - if (i > v4) - { - i -= v4; - pos += 16; - } - var v3 = (x3 >>> pos) & 0x000000ff; - if (i > v3) - { - i -= v3; - pos += 8; - } - var v2 = (x2 >>> pos) & 0x0000000f; - if (i > v2) - { - i -= v2; - pos += 4; - } - var v1 = (x1 >>> pos) & 0x00000003; - if (i > v1) - { - i -= v1; - pos += 2; - } - var v0 = (x >>> pos) & 0x00000001; - if (i > v0) - { - i -= v0; - pos += 1; - } - return pos; - } - - function dump () : string - { - var contents = [] : string[]; - contents.push(Binary.dump32bitNumber(this._size)); - contents.push(Binary.dump32bitNumberList(this._v)); - return contents.join(''); - } - - function dump (report : CompressionReport) : string - { - var contents = [] : string[]; - contents.push(Binary.dump32bitNumber(this._size)); - report.add(2, 2); - contents.push(Binary.dump32bitNumberList(this._v, report)); - return contents.join(''); - } - - function load (data : string) : int - { - return this.load(data, 0); - } - - function load (data : string, offset : int) : int - { - this.clear(); - this._size = Binary.load32bitNumber(data, offset); - var result = Binary.load32bitNumberList(data, offset + 2); - this._v = result.result; - this.build(); - return result.offset; - } -} -- cgit v1.2.3