How to encode integers into other integers

问题:

As a follow up to Store 2 4-bit numbers in 1 8 bit number, I am wondering if there is a generalization to it where you can store n x-bit numbers into m y-bit numbers. For example, maybe you can store 5 8 bit numbers into 3 15-bit numbers. Or maybe 2 8-bit numbers into 1 16 bit number, or 3 16 bit numbers into 2 32 bit numbers. Wondering what the implementation would be for encoding and decoding for a procedure that did this, or if it's not possible.

Something like:

function encode(i, s1, n, s2) {
  // i = array of input bytes
  // s1 = size of input bytes
  // n = number of output bytes
  // s2 = size of output bytes
}

function decode(i, s1, n, s2) {

}

回答1:

The general case is "streaming", which works no matter how badly misaligned everything gets. As usual, it pays for generality by being less efficient. It basically works by dropping input into a buffer until at least once chunk of output can be extracted from it and then extracting all the output, so something like this:

buffer = 0
bbits = 0
mask = (1 << outSize) - 1
while more input:
    while bbits < outSize:
        buffer |= in() << bbits
        bbits += inSize
    while bbits >= outSize:
        out(buffer & mask)
        buffer >>= outSize
        bbits -= outSize
if bbits != 0:
    out(buffer & mask)

Encoding and decoding is conceptually the same, but with the sizes swapped. When specialized to specific sizes of input and output chunk, one of the inner loops will not be a loop. An other packing order could be used too, outputting the high bits of a chunk of input before the low bits, whichever you like.

The size of the buffer must be at least outSize - 1 + inSize, to accommodate reading input after the maximum number of bits is left over after outputting from the buffer.

The sizes can even be changed during the procedure.