Using integers as bitfields in JavaScript

Question

As part of a project I have a string of numbers between 0 and 3, for example: 2030000000000000000030000000000000000003333212111221121301

I want to pass this string through an URL, so I figured I could try using a bitfield since each number only uses a maximum of 2 bits each. I wrote the following functions in my class to convert such a string to and from an array of integers used as bitfields for the data:

makeBuildBitfield: function(build) {
var b = build.split('');
var f = [3, 0]; // the "3" is there for future purposes
var i = 1;
var j = 0;

for (var t in b) {
    if (j < 14) {
        f[i] |= b[t];
        f[i] = f[i] << 2;
        ++j;
    } else {
        f[i] |= b[t];
        ++i;
        f[i] = 0;
        j = 0;
    }
}

return f.join('.');
},

getBuildFromBitfield: function(bitfield) {
b = bitfield.split('.');

var ba = [];
for (var x = 1; x < b.length; ++x) { //start from 1 to skip the "3"
    ba[x] = [];
    var n = b[x];
    for (var y = 14; y >= 0; --y) {
        ba[x][y] = n & 3;
        n = n >>> 2;
    }
}

build = '';
for (var a in ba) build += ba[a].join('');
return build;
},

They do seem to be working, but... not quite. When i pass the string from my example at the start:

2030000000000000000030000000000000000003333212111221121301

I get the following output:

3.587202560.786432.4089.156916164

However, when I pass this to the function that is supposed to convert it back, it gives me this:

203000000000000000003000000000000000000333321021112211213010

Note the extra zeros in the second string. Now, I'm new to operating on bits and this is my first attempt at it, but I've searched around and read the articles I could find on the subject, and I've tried to write down on a sheet of paper the state of the bits as the loop progresses to try and understand what is going on, but I just can't seem to figure out why it goes wrong and what those extra zeros are doing there. Either my string->bitfield function is off, or the other one, or quite possibly both. But I really can't figure it out, so does anyone have any suggestions as to how I could fix whatever it is that's going wrong?

Thanks in advance!

Answer 1

Here's a nice short approach that shrinks the bitfields to base-36 strings. It would work with base-10 strings too, but this is a little more condensed. It also works with leading zeros in the bitfield.

function shrink (s) {
  for (var p=0, l=s.length, r=''; p<l; p+=25) { 
    r+=parseInt('1'+s.substring(p,p+25),4).toString(36); 
  }
  return r;
}

function expand (s) {
  for (var p=0, l=s.length, r=''; p<l; p+=10) { 
    r+=parseInt(s.substring(p,p+10), 36).toString(4).substring(1);
  }
  return r;
}

Edit - I'm assuming your goal is to shrink the bitfield, send it through the url (a GET request), and then expand it on the other side. This will allow you to do that, although you won't be able to do anything useful with the shrunk data besides transport it and expand it.

Edit 2 - This is now a "no-dots" variation. Here's a test:

var bits =  "0000000000000000000000000000000032222000" +
            "0000000000000000000000000000000031111300" +
            "0000000000000000000002111300000002111200" +
            "0000000000000000000003111120000003111130" +
            "0000000000000000000000021111200000111120" +
            "0000000000000320000000000211112000311110" +
            "0000000000002111123000000031111130011113" +
            "0000000000000321111111230000311112031111" +
            "0000000000000000032111111123002112200000" +
            "0000000032223300000000021111112000000000" +
            "0000000021111111112233000332130000000000" +
            "0330000000033322111111111111003330000000" +
            "2112000000000000000003222112001113000000" +
            "2112000111111111111112222220001113000000" +
            "2112000222222111111111111120001113000000" +
            "2112000000000000000033222230001113000000" +
            "2112003111111111111111111120001113000000" +
            "2112000000000000000000000000001113000000" +
            "2112333333333333333333333333331113000000" +
            "2111111111111111111111111111111113000000" ;

var shrunk = shrink(bits);
// b33j9ynrb4b34c70cb9cb33j9ynrclf2iv9lsx6ocpgnayh8n4b33j9ys...

var restored = expand(shrunk);

alert ( "Worked: " + (bits===restored) + ", orig size: " 
      + bits.length + ", shrunk size: " + shrunk.length);

// Worked: true, orig size: 800, shrunk size: 320

Answer 2

There are several problems:

1. Don't use the "for (var x in y)" type of loop when iterating over arrays. Always use an index.

2. The last thing added to the bitfield string won't always represent 15 digits from the original. The "get" function always assumes that each bitfield component has the same number of digits.

3. You've left out var in some of your local variable declarations.

Here's my version, which works on your sample input at least:

  makeBuildBitfield: function(build) {
    var b = build.split('');
    var f = [3, 0]; // the "3" is there for future purposes
    var i = 1, j = 0;;

    for (var t = 0; t < b.length; ++t, ++j) {
        if (j === 15) {
          f[++i] = 0;
          j = 0;
        }
        f[i] = (f[i] << 2) + (b[t] & 3);
    }

    f[0] = j === 0 ? 15 : j;
    return f.join('.');
  },

  getBuildFromBitfield: function(bitfield) {
    var b = bitfield.split('.');

    var ba = [];
    for (var x = 1; x < b.length; ++x) { //start from 1 to skip the "3"
        ba[x] = [];
        var n = b[x];
        for (var y = (x === b.length - 1 ? parseInt(b[0], 10) : 15); --y >= 0; ) {
            ba[x][y] = n & 3;
            n = n >>> 2;
        }
    }

    var build = '';
    for (var a = 1; a < ba.length; ++a) {
      build += ba[a].join('');
    }
    return build;
  }

I stole your "f[0]" for the size of the last entry, but you could put the value anywhere.

Answer 3

Well since I already have some bitmap code already written, here's a solution using it.

Bitmap.js

function Bitmap (vals) {
  this.arr = [];
  this.length = 0;
  if (vals) {
    for (var i = vals.length - 1; i >= 0; --i) {
      if (vals [i]) {
        this.set (i);
      }
      else {
        this.clear (i);
      }
    }
  }
}

Bitmap.prototype = {
    constructor: Bitmap

  , toString: function () {
      vals = [];
      for (var i = this.length - 1; i >= 0; --i) {
        vals [i] = this.get (i) ? "1" : "0";
      }
      return vals.join ("");
    }

  , clear: function (i) {
      if (i >= this.length) {
        this.length = i + 1;
      }
      var pos = i / 32 | 0;
      this.arr [pos] = this.arr [pos] & ~(1 << i % 32);
    }

  , get: function (i) {
      return (this.arr [Math.floor (i / 32 | 0)] & 1 << i % 32) > 0;
    }

  , serialize: function () {
      var str = "";
      for (var i = 0; i < this.arr.length; ++i) {
        var num = this.arr [i];
        str += num < 0
          ? (-num).toString (36) + Bitmap.NEGATIVE_DELIM
          : num.toString (36) + Bitmap.POSITIVE_DELIM
          ;
      }
      var trailingLength = this.length % 32;
      if (trailingLength == 0) {
        trailingLength = 32;
      }
      if (this.length == 0) {
        trailingLength = 0;
      }
      return str + trailingLength.toString (36);
    }

  , set: function (i) {
      if (i >= this.length) {
        this.length = i + 1;
      }
      var pos = i / 32 | 0;
      this.arr [pos] = this.arr [pos] | 1 << i % 32;
    }

  , size: function () {
      return this.length;
    }

};

Bitmap.POSITIVE_DELIM = ".";
Bitmap.NEGATIVE_DELIM = "!"

Bitmap.deserialize = (function () {
  var MATCH_REGEX = new RegExp (
      "[A-Za-z0-9]+(?:"
      + Bitmap.POSITIVE_DELIM
      + "|"
      + Bitmap.NEGATIVE_DELIM
      + ")?"
    , "g");
  return function (str) {
    var bm = new Bitmap ();
    var arr = str.match (MATCH_REGEX);
    var trailingLength = parseInt (arr.pop (), 36);
    for (var i = 0; i < arr.length; ++i) {
      var str = arr [i];
      var sign = str.charAt (str.length - 1) == Bitmap.POSITIVE_DELIM ? 1 : -1;
      bm.arr [i] = parseInt (str, 36) * sign;
    }
    bm.length = Math.max ((arr.length - 1) * 32 + trailingLength, 0);
    return bm;
  };
}) ();

Test.js

function toBits (numStr, numBitsToExtract) {
  var numChars = numStr.split ("");
  var bits = [];
  for (var i = 0; i < numChars.length; ++i) {
    var num = numChars [i] - 0;
    for (var j = numBitsToExtract - 1; j >= 0; --j) {
      bits.push (num & 1 << j ? 1 : 0);
    }
  }
  return bits;
}

function fromBits (bitStr, numBitsToExtract) {
  var bitChars = bitStr.split ("");
  var nums = [];
  for (var i = 0; i < bitChars.length; ) {
    var num = 0;
    for (var j = numBitsToExtract - 1; j >= 0; ++i, --j) {
      num |= bitChars [i] - 0 << j;
    }
    nums.push (num);
  }
  return nums.join ("");
}

var numStr = "2030000000000000000030000000000000000003333212111221121301";
var bits = toBits (numStr, 2);
var serialized = new Bitmap (bits).serialize (); // "1d.lc.ou00e8!ci3a.k"
var recoveredNumStr = fromBits (Bitmap.deserialize (serialized).toString (), 2);