Merging upstream version 1.44.3.

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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;
+    }
+}