Как кодировать целые числа в другие целые числа?

В качестве продолжения сохраните 2 4-битных числа в 1 8-битное число, мне интересно, есть ли для него обобщение, в котором вы можете хранить n x-битных чисел в m y-битных числах. Например, возможно, вы можете сохранить 5 8-битных чисел в 3 15-битных числах. Или, может быть, 2 8-битных числа в 1 16-битном числе или 3 16-битных числа в 2 32-битных числах. Интересно, какой будет реализация для кодирования и декодирования для процедуры, которая это сделала, или если это невозможно.

Что-то типа:

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) {

}

Основываясь на приведенном ниже ответе, я попытался перевести его на JavaScript, но не понимаю, что на самом деле означает, и не думаю, что это работает.

function encode(input, inputSize, outputSize, callback) {
  var buffer = 0
  var bbits = 0
  var mask = (1 << outputSize) - 1
  while (bbits < outputSize) {
    buffer |= (input << bbits)
    bbits += inputSize
  }
  while (bbits >= outputSize) {
    callback(buffer & mask)
    buffer >>= outputSize
    bbits -= outputSize
  }
}

person Lance Pollard    schedule 07.07.2018    source источник


Ответы (2)


Вы не можете сохранить 5 8-битных чисел в 3 15-битных числах, потому что 45 бит информации явно не помещаются в 40 битах памяти. Вы можете сделать это только в том случае, если общее количество вариантов меньше или равно 2k, где k – это количество битов, используемых для кодирования.

Если ширина каждого значения одинакова, то вот моя попытка, которая хранит биты линейно в обратном порядке. Функция кодирования переводит биты в массиве байтов в другой массив, который хранит полное значение в bitLength битах, а функция декодирования делает обратное.

function encode(input, bitLength) {
  // size of each array element must be greater than bitLength
  var output = new Uint16Array(Math.ceil(input.length * 8 / bitLength));
  var remainingBits = bitLength; // the remaining bits left for the current value

  // example when bitLength = 11
  //       start of current value
  //       │          next value
  //       │2345678901│
  // ...┆  ↓    ┆     ↓ ┆       ┆       ┆       ┆...      ← input bytes
  // ...₀₁₂₃₄₅₆₇⁰¹²³⁴⁵⁶⁷₀₁₂₃₄₅₆₇⁰¹²³⁴⁵⁶⁷₀₁₂₃₄₅₆₇ ...      ← bit position

  for (var inIdx = 0, outIdx = 0; inIdx < input.length; inIdx++) {
    if (remainingBits > 8) {
      output[outIdx] = (output[outIdx] << 8) | input[inIdx];
      remainingBits -= 8;               // 8 less bits to read
    } else if (remainingBits == 8) {    // finish current value
      output[outIdx] = (output[outIdx] << 8) | input[inIdx];
      remainingBits = bitLength; // next byte is the start of the next output value
      outIdx++;
    } else {
      var nextRemainingBits = 8 - remainingBits;
      output[outIdx] = (output[outIdx] << remainingBits)
                     | (input[inIdx] >>> nextRemainingBits);
      // the leftover bits (nextRemainingBits) in the input byte
      // go into the next output
      output[++outIdx] = input[inIdx] & ((1 << nextRemainingBits) - 1);
      // adjust the number of remaining bits, after we've read
      // `8 - remainingBits` bits for the current output
      remainingBits = bitLength - nextRemainingBits;
    }
  }
  return output;
}

function decode(input, bitLength) {
    const numBits = input.BYTES_PER_ELEMENT*8;
  var output = new Uint8Array(Math.ceil(input.length * bitLength / 8));
  var remainingInputBits = bitLength; // the remaining bits left for the current value
  
  // shift value to the most significant position
  for (var i = 0; i < input.length; i++)
    input[i] <<= numBits - bitLength;
  
  for (var inIdx = 0, outIdx = 0; outIdx < output.length; outIdx++) {
    if (remainingInputBits > 8) {
      output[outIdx] = input[inIdx] >>> (numBits - 8);  // get the top byte from input
      input[inIdx] <<= 8;   // shift the read bits out, leaving next bits on top
      remainingInputBits -= 8;
    } else if (remainingInputBits == 8) {
      output[outIdx] = input[inIdx] >>> (numBits - 8);
      remainingInputBits = bitLength;
      inIdx++;
    } else {
      remainingInputBits = 8 - remainingInputBits;
      output[outIdx] = input[inIdx] >>> (numBits - 8);
      inIdx++;
      output[outIdx] |= input[inIdx] >>> (numBits - remainingInputBits);
      input[inIdx] <<= remainingInputBits;
      remainingInputBits = bitLength - remainingInputBits;
    }
  }
  return output;
}

function pad(s, size) {
  s = (s >>> 0).toString(2);
  while (s.length < (size || 2)) { s = "0" + s; }
  return s;
}

function printBinaryArray(arr, padLength) {
    var str = "";
    for (var i = 0; i < arr.length; i++)
        str += pad(arr[i], padLength) + " ";
    console.log(str);
}

var inputBytes = 22;
var bitLength = 11; // each value is 11-bit long
var input = new Uint8Array(inputBytes);

window.crypto.getRandomValues(input);

var encodedData = encode(input, bitLength);
console.log("Input data", input);
printBinaryArray(input, 8);
console.log("Encoded data");
// console.log(encodedData);
printBinaryArray(encodedData, bitLength);

var decodedData = decode(encodedData, bitLength);
console.log("Decoded data", decodedData);
printBinaryArray(decodedData, 8);

for (var i = 0; i < input.length; i++)
    if (input[i] != decodedData[i])
        console.log("Wrong decoded data");
console.log("Data decoded successfully");

На самом деле процедуры кодирования и декодирования просто обратны друг другу, поэтому вы можете легко изменить их на encode(input, inputBitWidth, outputBitWidth), которые можно использовать как для кодирования, так и для декодирования, просто поменяйте местами входную и выходную ширину.

Однако для значений нечетного размера часто лучше упаковывать старшие биты вместе для облегчения доступа. Например, форматы 10-битных пикселей часто упаковывают 4 пикселя в 5-байтовую группу, причем 8 старших битов каждого пикселя находятся в первых 4 байтах, а последний байт содержит 2 младших бита для них.

Смотрите также

person phuclv    schedule 16.03.2019

Общим случаем является «потоковая передача», которая работает независимо от того, насколько сильно все смещено. Как обычно, он платит за универсальность меньшей эффективностью. В основном он работает, помещая входные данные в буфер до тех пор, пока из него не будет извлечен хотя бы один фрагмент вывода, а затем извлекается весь вывод, поэтому что-то вроде этого:

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)

Кодирование и декодирование концептуально одинаковы, но размеры меняются местами. При специализации на определенные размеры входных и выходных фрагментов один из внутренних циклов не будет циклом. Можно использовать и другой порядок упаковки, выводя старшие биты блока ввода перед младшими битами, в зависимости от того, что вам нравится.

Размер буфера должен быть не менее outSize - 1 + inSize, чтобы обеспечить возможность чтения ввода после того, как после вывода из буфера останется максимальное количество битов.

Размеры можно менять даже во время процедуры.

person harold    schedule 07.07.2018
comment
Интересно, не могли бы вы создать пример JavaScript для этого, я не смог точно понять, как это перевести :) - person Lance Pollard; 27.08.2018
comment
Я не понимаю, что такое bbits, но я думаю, что у меня есть остальная часть входной кодировки. Было бы полезно узнать кодировку вывода: gist.github.com/lancejpollard/7609f20cfbf1d568e9fb3d298ab20034, и может быть, объяснение того, как это работает, происходит много махинаций, в которых я не слишком разбираюсь. Спасибо за помощь. Мой импл переходит в бесконечный цикл, лол. - person Lance Pollard; 27.08.2018
comment
@LancePollard bbits — это количество битов, которые в данный момент буферизуются. Хотя я не сразу понимаю, почему существует бесконечный цикл, я вижу некоторые отличия во втором цикле while. - person harold; 27.08.2018
comment
Я до сих пор не понимаю, как это использовать :/ - person Lance Pollard; 11.03.2019