Fastest way to pack two nibbles into one byte

Question

What would be the fastest way to pack two bytes into one? I have a large array of bytes. Each byte represents a number not larger than 15 (4-bit number). Because of that I could pack two bytes into one, placing the first byte into the higher nibble and the later in to the lower nibble.

My current approach is to create a second array half the size of the original and then to iterate over the original array shifting it and | to get the nibbles. This works however it takes a while depending on the size of the array. The arrays are from a few thousand entries to a few million. It's not catastrophic but any optimization would be helpful

Answer 1

It will obviously take a while if your array is large - you need to go over all of it.

First thing I'd do is create a lookup table from two bytes to one, so you don't need to shift and or - take the next two bytes, look up their offset and get the resulting byte.

This lookup table should have 2^12 entries (you only need 4 bytes from the most significant byte), and fit nicely in your CPU's L1 cache. It might be faster than shift-and-or.

On the other hand, if you load 8 bytes at a time (on a 64 bit CPU, as they all are nowadays), you can turn it into 4 bytes and store them. You will be able to parallelize this (divide the array into 4 parts, and have each core handle one part).

If there were an instructions that takes bytes 0, 2, 4 and 6 from a 64-bit register and puts them in a 32 bit register, you'd be done.

UPDATE: You mentioned in the question you have a few million bytes. In that case, don't bother. The difference between highly optimized assembly and the naive implementation in C is not going to be worth the trouble. Just load the data two bytes at a time, shift and or two nibbles into one byte and store in the target array. Processing 1MB of data should be instant.