diff options
Diffstat (limited to 'web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx')
-rw-r--r-- | web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx | 295 |
1 files changed, 295 insertions, 0 deletions
diff --git a/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx b/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx new file mode 100644 index 000000000..b366e43a0 --- /dev/null +++ b/web/server/h2o/libh2o/misc/oktavia/src/bit-vector.jsx @@ -0,0 +1,295 @@ +/** + * 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; + } +} |