Должен ли я обеспечивать проверки согласованности в алгоритме построения дерева Хаффмана для DEFLATE?

В RFC-1951 есть простой алгоритм, восстанавливающий дерево Хаффмана из списка длин кодов, описанный следующим образом:

     1)  Count the number of codes for each code length.  Let
         bl_count[N] be the number of codes of length N, N >= 1.

     2)  Find the numerical value of the smallest code for each
         code length:

            code = 0;
            bl_count[0] = 0;
            for (bits = 1; bits <= MAX_BITS; bits++) {
                code = (code + bl_count[bits-1]) << 1;
                next_code[bits] = code;
            }

     3)  Assign numerical values to all codes, using consecutive
         values for all codes of the same length with the base
         values determined at step 2. Codes that are never used
         (which have a bit length of zero) must not be assigned a
         value.

            for (n = 0;  n <= max_code; n++) {
                len = tree[n].Len;
                if (len != 0) {
                    tree[n].Code = next_code[len];
                    next_code[len]++;
                }

Но никаких проверок согласованности данных в алгоритме нет. С другой стороны, очевидно, что список длин может быть недействительным. Значения длины из-за кодирования в 4 бита не могут быть недействительными, но, например, кодов может быть больше, чем может быть закодировано для некоторой длины кода.

Какой минимальный набор проверок обеспечит валидацию данных? Или такие проверки не нужны по какой-то причине, которую я пропустил?


validation algorithm language-agnostic deflate
person johnfound    schedule 28.10.2014    source источник

Ответы (3)


arrow_upward
1
arrow_downward

zlib проверяет, что список длин кода является полным, т. е. что он использует все битовые комбинации, и что он не переполняет битовые комбинации. Единственным допустимым исключением является наличие одного символа длиной 1, и в этом случае код может быть неполным (бит 0 означает, что символ, бит 1 не определен).

Это помогает zlib отклонять случайные, поврежденные или неправильно закодированные данные с большей вероятностью и раньше в потоке. Это другой тип надежности, чем то, что было предложено в другом ответе здесь, где вы могли бы альтернативно разрешать неполные коды и возвращать ошибку только тогда, когда в сжатых данных встречается неопределенный код.

Чтобы вычислить полноту, вы начинаете с количества битов в коде k=1 и количества возможных кодов n=2. Возможны два однобитных кода. Вы вычитаете из n количество кодов длины 1, n -= a[k]. Затем вы увеличиваете k для просмотра двухбитных кодов и удваиваете n. Вычтите количество двухбитных кодов. Когда вы закончите, n должно быть равно нулю. Если в какой-то момент n станет отрицательным, вы можете остановиться прямо здесь, поскольку у вас есть недопустимый набор длин кода. Если, когда вы закончите, n больше нуля, то у вас неполный код.

person Mark Adler    schedule 28.10.2014
comment
Я немного смущен здесь. Является ли [] равным bl_count[] из RFC-1951? - person johnfound; 28.10.2014
comment
Что ж, я проверил это, и этот способ действительно прост. Для сборки потребовалось всего 5 дополнительных инструкций. В любом случае, должен ли я обрабатывать 1-битное исключение, о котором вы упомянули? И почему разрешено это исключение? - person johnfound; 28.10.2014
comment
Это разрешено, потому что исходная спецификация PKZIP для формата deflate допускает это в случае одного кода расстояния. Я считаю это ошибкой, так как если есть только один возможный код, то для его кодирования нужно ноль битов, а не один. Однако Фил Кац (PK в PKZIP) решил сделать его однобитным, а не нулевым. - person Mark Adler; 28.10.2014
comment
Это исключение стоит мне больше кода, чем общий алгоритм... :*( В любом случае, спасибо за большую помощь. :) - person johnfound; 28.10.2014
comment
Что касается времени выполнения, вы можете подождать с проверкой исключения до тех пор, пока не определите, что код неполный. - person Mark Adler; 28.10.2014
comment
Ну, на самом деле это не имеет большого значения. Я просто хотел уместить код в 170 байт, чтобы иметь проверку на непротиворечивость и при этом построить настоящую древовидную структуру, чтобы позже ускорить декодирование. Во всяком случае, теперь я реализовал его в 180 байт, и он все еще довольно хорош для моих целей. - person johnfound; 28.10.2014
comment
Кроме того, я выделяю память для дерева Хаффмана в соответствии с предположением, что дерево является полным бинарным деревом. Разрешение неполных деревьев потребует больше памяти для структуры узлов, что может привести к переполнению буфера. - person johnfound; 29.10.2014
comment
Единственным неполным деревом, которое должно быть разрешено, является один узел для одного символа с однобитовым кодом (0). Это не должно привести к тому, что вам понадобится дополнительная память. - person Mark Adler; 30.10.2014
comment
Да, в самом деле. Это именно то, что я сделал. Кстати, код для этой процедуры готов и работает как положено: Здесь - person johnfound; 30.10.2014

arrow_upward
1
arrow_downward

Я думаю, что проверки того, что next_code[len] не выходит за пределы соответствующих битов, достаточно. Итак, после tree[n].Code = next_code[len]; вы можете выполнить следующую проверку:

if (tree[n].Code & ((1<<len)-1) == 0)
    print(Error)

Если tree[n].Code & ((1<<len)-1) достигает 0, это означает, что кодов длины len больше, чем должно, поэтому в списке длин была ошибка. С другой стороны, если каждому символу дерева присвоен действительный (уникальный) код, то вы создали правильное дерево Хаффмана.

РЕДАКТИРОВАТЬ: Меня только что осенило: вы можете просто сделать ту же проверку в конце первого шага: вам просто нужно проверить, что bl_count[N] <= 2^N - SUM((2^j)*bl_count[N-j]) для всех 1<=j<=N и для всех N >=1 (если бинарное дерево имеет bl_count[N-1] листьев на уровне N-1, то оно не может иметь более 2^N - 2*bl_count[N-1] листьев на уровне N, причем уровень 0 является корнем).

Это гарантирует, что код, который вы создаете, является кодом префикса, но не гарантирует, что он такой же, как задумал первоначальный создатель. Если, например, список длин недействителен таким образом, что вы все еще можете создать действительный код префикса, вы не можете доказать, что это код Хаффмана, просто потому, что вы не знаете частоту появления каждого символа.

person Cantfindname    schedule 28.10.2014
comment
Да, этот подход кажется правильным. Но нельзя ли перенести эту проверку на этап 2 или этап 1 алгоритма. Это не так важно, но на этапе 3 я уже выделил память под дерево и при ошибке должен ее освободить. - person johnfound; 28.10.2014
comment
Вы также можете сделать это в конце шага 1, проверьте мою правку - person Cantfindname; 28.10.2014
comment
Хм, эта сумма немного напоминает то, что делается в петле этапа 2... Я должен немного помедитировать над этим. :) - person johnfound; 28.10.2014

arrow_upward
0
arrow_downward

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

На мой взгляд, вы должны попытаться обрабатывать недопустимые, но не опасные входные данные как можно изящнее, чтобы взаимодействовать с программами, написанными другими, которые могут интерпретировать спецификацию иначе, чем вы, или которые допустили небольшие ошибки, которые имеют только одну правдоподобную интерпретацию. Это принцип надежности. Вы можете найти обсуждение этого вопроса, начиная с http://en.wikipedia.org/wiki/Robustness_principle.

person mcdowella    schedule 28.10.2014
comment
Ну да, это общеизвестные правила. Но как лучше всего применить эти правила к конкретному коду из вопроса? - person johnfound; 28.10.2014