Swapping Nibbles

Question

I have small (<250 bytes) chunk of binary data, where I know that almost always, the first nibble is going to be zero 0. For example, in hex:

01 02 03 04 0A 0B 0C 0D

I want to do some simple compression on this data. What I've decided to do is run length encoding, but I first need to get the data such that all the expected zeroes are next to each other. To do this, I need to do a swap of the nibbles from one side of the array to the other. For example, using the array above, I'd end up with the result of:

00 00 00 00 4A 3B 2C 1D

This would make for efficient RLE.

Just to better illustrate, here's another example, this time without the zeroes in the array:

12 34 56 78 9A BC

After the "swap nibbles" algorithm:

1B 39 57 68 4A 2C

(And of course, running "swap nibbles" again reverses it, which is what I need.)

I've worked up a JavaScript solution for this, but it "feels" overly tricky. I'd love for someone to take a look and let me know if they have any suggestions, or a completely different idea entirely. To enumerate my requirements:

• Most significant nibbles clustered with each other
• Algorithm must be reverisble
• Should work with an arbitrary amount of data, including odd numbers of bytes (but expected always be a small amount of data, under 1 KB)

It is not a requirement that any solution use the exact same packing method I'm doing. Just as long as I get the the zeroes together, that's the main goal.

My Solution

/**
 * Redo the bytes so that the data for the most significant nibbles are in
 * the first half of the array, and the least significant nibbles are in the
 * last half of the array.  This makes for efficient packing when we know that
 * a lot of this data is going to be all zeroes.
 * @param {Uint8Array} data 
 */
function swapNibbles(data) {
  const newData = new Uint8Array(data.length);
  for (let i=0; i<data.length/2; i++) {
    // If odd number of bytes, and iterator is on the middle byte, just leave it
    if (i === (data.length - 1 - i)) {
      newData[i] = data[i];
    } else {
      // Left Side of Array (most significant nibbles)
      newData[i] = (
        // Most significant nibble of left byte
        (data[i] & 0xF0) + 

        // Most sigificant nibble of right byte, demoted by 4 bits
        ((data[data.length - 1 -i] & 0xF0) >> 4)
      );

      // Right Side of Array (least significant nibbles)
      newData[data.length - 1 - i] = (
        // Least significant nibble of left byte, promited by 4 bits
        ((data[i] & 0x0F) << 4) +

        // Least significant nibble of right byte
        (data[data.length - 1 -i] & 0x0F)
      );
    }
  }

  return newData;
}

Any feedback would be appreciated. Thanks!

Answer 1

I don't know too much about what you're trying to do (but it makes sense and I think I get it).

Personally my feeling is that all you are missing is the right helper functions to make your code more transparent. I don't know how efficient this should be and hence if the overhead of function calls matters to you, but I am guessing no as otherwise you would have transformed the data in place I imagine.

/**
 * Redo the bytes so that the data for the most significant nibbles are in
 * the first half of the array, and the least significant nibbles are in the
 * last half of the array.  This makes for efficient packing when we know that
 * a lot of this data is going to be all zeroes.
 * @param {Uint8Array} data
 */
function swapNibblePairs(data) {
    const newData = new Uint8Array(data);
    for (let i = 0; i < Math.floor(data.length / 2); i++) {
        const [hiNibbleLeft, loNibbleLeft] = getNibbles(data[i]);
        const [hiNibbleRight, loNibbleRight] = getNibbles(data[data.length - 1 - i]);

        newData[i] = byteFromNibbles(hiNibbleLeft, hiNibbleRight);
        newData[data.length - 1 - i] = byteFromNibbles(loNibbleLeft, loNibbleRight);
    }

    return newData;
}

function byteFromNibbles(hi, lo) {
    return (hi << 4) | lo;
}

function getNibbles(byte) {
    return [(byte >> 4) & 0x0f, byte & 0x0f];
}

The most important bit for me is it's now evident what the bytes you construct are, you take the two hi parts and join them, and take the two lo parts and join them.

It also makes it evident in the code that this function is its own inverse which is nice.