Сжатие массива элементов при уменьшении размера каждого элемента с 8 бит до 3 бит
У меня есть элементы внутри массива. Каждый элемент имеет размер 1 байт, то есть 8 бит. С помощью этого подхода я уменьшил каждый элемент с 8-битного до 3-битного: https://stackoverflow.com/a/78870606/3405291
Затем я собираюсь упаковать сжатые элементы в меньший массив, разделив 3-битные фрагменты между последовательными байтами.
Я ищу терминологию такого алгоритма. Есть ли какой-нибудь стандартный алгоритм для этого? Фрагмент кода/пример будет очень полезен.
Код
Это код Голанга, над которым я работаю:
type Span struct {
i0, i1 int // Start and end index of pixels inside a span
color uint8 // Color to be painted on pixels
}
func ShrinkPixelAndPaintColor(ss []Span, img *Image) {
var bit8 uint8
var bit3 uint8
for _, s := range ss {
i0 := s.i0
i1 := s.i1
for i := i0; i < i1; i += 1 {
bit8 = s.color
// Shrink/scale from 8 bits to 3 bits
// We scale 256 to 8, which is x*8/256, that reduces to x/2^5 or x>>5
bit3 = bit8 >> 5
img.Pix[i] = uint8(bit3)
// TODO: How to compact the pixels so that
// we actually benefit from the shrinkage to
// reduce memory usage for huge 32K images?
}
}
}
@MrSmith42 MrSmith42 Мне придется разделить 3 бита между байтами памяти, и это, я думаю, причина сложности для меня.
Терминология, которую вы ищете, — Bit Packing (связанный вопрос ). Возможно, вам будет интересно посмотреть, как реализовано кодирование Base64, поскольку оно преобразует 6-битные поля в массивы 8-битных байтов.
@Вик Спасибо. Я собираюсь взглянуть.
@Megidd: Я имел в виду, что в зависимости от языка, который вы будете использовать для реализации, способ использования длинного (64 бита) и траты 1 его бита позволит избежать необходимости собирать биты из более чем одной переменной (длинный в в этом случае) и поэтому его будет очень просто реализовать.
@ MrSmith42 Ага, теперь я понял. Похоже, это хорошая идея :) Потеря одного бита на каждые 64 бита может быть приемлемой.
@MrSmith42 MrSmith42 Я думал об этом. Я работаю с пикселями изображения. Пиксели изображения идут последовательно один за другим. Между данными пикселей не может быть никакого разрыва — даже одного бита.
Что вы будете делать с остатком, если последние 3 бита не совпадают с границей байта? И как вы будете определять, действительно ли биты являются данными или это просто неиспользуемые биты в конце?
@trincot Все оставшиеся биты равны нулю. По умолчанию пиксели имеют нулевые значения, если только я не заполню их каким-либо цветом, то есть ненулевыми данными. Я работаю с пикселями изображения.
Тот же метод, что и в этом ответе: stackoverflow.com/questions/76139828/…
Ответы 1
В C вы можете сделать это следующим образом:
void pack(unsigned char *arr, size_t len, unsigned char *result) {
size_t num_bytes = (len * 3 + 7) >> 3;
size_t j = 0;
char shift = 5;
for (size_t i = 0; i < len; i++) {
unsigned char color = arr[i] >> 5;
if (shift < 0) {
result[j] |= color >> -shift;
j++;
shift += 8;
}
result[j] |= color << shift;
shift -= 3;
}
}
Итак, здесь входные данные задаются как массив байтов (unsigned char) и его длины, а выходные данные записываются в result, который должен быть инициализирован 0 и иметь размер, соответствующий num_bytes.
Вот пример вызова:
int main(void) {
unsigned char arr[8] = {0xFF, 0x33, 0x66, 0x88, 0x22, 0x99, 0x11, 0x77};
unsigned char result[3] = {0};
pack(arr, 8, result);
// Verify that result is as expected
if (result[0] == 0xE5 && result[1] == 0xC3 && result[2] == 0x03 ) {
printf("test passed.\n");
} else {
printf("test failed.\n");
}
return 0;
}
Я тестировал эту игровую площадку C, она прошла тест, спасибо :)
Я дважды проверил 6 полубайт массива result, как показано ниже. Делюсь на будущее: golang const b1 = 0b1110 const x1 = 0xe const b2 = 0b0101 const x2 = 0x5 const b3 = 0b1100 const x3 = 0xc const b4 = 0b0011 const x4 = 0x3 const b5 = 0b0000 const x5 = 0x0 const b6 = 0b0011 const x6 = 0x3
Маскируйте и сдвигайте интересующие вас биты. Не уверен, стоит ли это называть алгоритмом. Если вы собираетесь разделить 3 бита между двумя частями памяти, это немного сложнее, чем просто сохранить 21 из них в 64-битной переменной и потратить один бит впустую.