Величина змінної довжини

Вказівки

Реалізуйте кодування та декодування величини змінної довжини.

Мета цієї вправи - реалізувати кодування та декодування VLQ.

Коротко кажучи, мета цього кодування - закодувати цілі числа так, щоб зекономити байти. Значущими є лише перші 7 бітів кожного байта (вирівняні по правому краю; приблизно як у байті ASCII). Отже, якщо ми маємо 32-бітне значення, його потрібно розпакувати в послідовність 7-бітних байтів. Звісно, кількість байтів буде різною залежно від нашого цілого числа. Щоб позначити, який байт є останнім у послідовності, ми залишаємо біт №7 нульовим. У всіх попередніх байтах ми встановлюємо біт №7.

Отже, якщо ціле число лежить у межах 0-127, його можна подати одним байтом. Хоча VLQ може працювати з числами довільного розміру, у цій вправі ми обмежимося лише числами, які вміщуються в 32-бітне беззнакове ціле число. Ось приклади цілих чисел як 32-бітних значень і величини змінної довжини, у які вони перетворюються:

 NUMBER        VARIABLE QUANTITY
00000000              00
00000040              40
0000007F              7F
00000080             81 00
00002000             C0 00
00003FFF             FF 7F
00004000           81 80 00
00100000           C0 80 00
001FFFFF           FF FF 7F
00200000          81 80 80 00
08000000          C0 80 80 00
0FFFFFFF          FF FF FF 7F

---

Джерело

Бідолашний розробник зі Splice, якому довелося реалізувати кодування й декодування MIDI.