Há muito tempo me pergunto como os dados são compactados, inclusive nos arquivos Zip. Certa vez, decidi satisfazer minha curiosidade: aprender como a compactação funciona e escrever meu próprio programa Zip. A implementação se tornou um exercício emocionante de programação. Você tem o prazer de criar uma máquina depurada que coleta dados, transfere seus bits para uma representação mais eficiente e depois os coleta novamente. Espero que você também esteja interessado em ler sobre isso.O artigo explica detalhadamente como os arquivos Zip e o esquema de compactação funcionam: compactação LZ77, algoritmo Huffman, algoritmo Deflate e muito mais. Você aprenderá o histórico do desenvolvimento da tecnologia e verá exemplos de implementação bastante eficazes, escritos do zero em C. O código-fonte está aqui: hwzip-1.0.zip .Sou muito grato a Ange Albertini , Gynvael Coldwind , Fabian Giesen , Jonas Skeppstedt ( web ), Primiano Tucci e Nico Weber , que forneceram comentários valiosos sobre os rascunhos deste artigo.Conteúdo
História
PKZip
Nos anos oitenta e início dos anos noventa, antes da disseminação da Internet, os entusiastas da computação usavam modems dial-up para conectar-se via rede telefônica à rede BBS (Bulletin Board Systems). O BBS era um sistema de computador interativo que permitia aos usuários enviar mensagens, jogar e compartilhar arquivos. Para ficar online, bastava ter um computador, modem e um bom número de telefone BBS. Os números foram publicados em revistas de informática e em outros BBS.Uma ferramenta importante para facilitar a distribuição de arquivos foi o arquivador . Permite salvar um ou mais arquivos em um único arquivo mortopara armazenar ou transmitir informações de maneira mais conveniente. E, idealmente, o arquivo compactado também compactou arquivos para economizar espaço e tempo para transmissão pela rede. Nos dias da BBS, o arquivador Arc era popular, escrito por Tom Henderson, da System Enhancement Associates (SEA), uma pequena empresa que ele fundou com seu cunhado.No final dos anos 80, o programador Phil Katz lançou sua própria versão do Arc, PKArc. Era compatível com o SEA Arc, mas funcionava mais rápido graças às sub-rotinas escritas em linguagem assembly e usava um novo método de compactação. O programa tornou-se popular, Katz largou o emprego e criou o PKWare para se concentrar em novos desenvolvimentos. Segundo a lenda, a maior parte do trabalho ocorreu na cozinha de sua mãe em Glendale, Wisconsin.Foto de Phil Katz de um artigo no Milwaukee Sentinel , em 19 de setembro de 1994.No entanto, o SEA não ficou satisfeito com a iniciativa de Katz. A empresa o acusou de violação de marca registrada e direitos autorais. Os litígios e controvérsias na rede BBS e no mundo dos PCs ficaram conhecidos como Arc Wars . No final, a disputa foi resolvida em favor da AAE.Abandonando o Arco, Katz criou um novo formato de arquivamento em 1989, que ele chamou de Zip e disponibilizou ao público :, , , . , ".ZIP", , , , , , , , , .
O programa de Katz para criar esses arquivos foi chamado PKZip e logo se espalhou pelo mundo do BBS e PC.Um dos aspectos que provavelmente contribuiu para o sucesso do formato Zip é que a documentação veio com o PKZip, Nota de Aplicação , que explicava em detalhes como o formato funciona. Isso permitiu que outras pessoas aprendessem o formato e criassem programas que geram, extraem ou interagem com os arquivos Zip.Zip - um formato de compactação sem perda : após a descompactação, os dados serão os mesmos de antes da compactação. O algoritmo busca redundância nos dados de origem e apresenta informações com mais eficiência. Essa abordagem é diferente da compactação com perdas., que é usado em formatos como JPEG e MP3: quando compactados, algumas das informações menos visíveis ao olho ou ouvido humano são descartadas.O PKZip foi distribuído como Shareware: poderia ser usado e copiado livremente, mas o autor sugeriu que os usuários “registrassem” o programa. Por US $ 47, você pode obter instruções impressas, suporte premium e uma versão aprimorada do aplicativo.Uma das principais versões do PKZip foi a 2.04c, lançada em 28 de dezembro de 1992 (a versão 2.04g foi lançada logo após ). Ele usou o algoritmo de compactação Deflate padrão. A versão determinou o desenvolvimento adicional da compactação em arquivos Zip ( artigo dedicado ao lançamento ).Desde então, o formato zip tem sido usado em muitos outros formatos de arquivo. Por exemplo, arquivos Java (.jar), pacotes de aplicativos Android (.apk) e arquivos .docx do Microsoft Office usam o formato Zip. Muitos formatos e protocolos usam o mesmo algoritmo de compactação, Deflate. Digamos, as páginas da web provavelmente são transferidas para o seu navegador como um arquivo gzip, cujo formato usa a compactação Deflate.Phil Katz morreu em 2000. O PKWare ainda existe e suporta o formato Zip, embora a empresa se concentre principalmente no software de proteção de dados.Info-zip e zlib
Logo após o lançamento do PKZip em 1989, outros programas para descompactar arquivos Zip começaram a aparecer. Por exemplo, um programa de descompactação que pode ser descompactado em sistemas Unix. Em março de 1990, uma lista de endereços chamada Info-ZIP foi criada.O grupo Info-ZIP lançou programas de código aberto gratuitos, descompacte e zip , que foram usados para descompactar e criar arquivos zip. O código foi portado para muitos sistemas e ainda é o padrão para programas Zip para sistemas Unix. Isso mais tarde ajudou a aumentar a popularidade dos arquivos Zip.Depois que o código Info-ZIP que desinflou a compactação e descompactação foi movido para uma biblioteca zlib separada que eles escreveramJean-loup Gailly (compressão) e Mark Adler (desembalagem).Jean-loup Gailly (à esquerda) e Mark Adler (à direita) no USENIX STUG Award 2009.Um dos motivos para a criação da biblioteca foi o fato de fornecer a conveniência de usar a compactação Deflate em outros aplicativos e formatos, por exemplo, no novo gzip e PNG . Esses novos formatos pretendiam substituir o Compress e o GIF , que usavam o algoritmo LZW protegido por patente.Como parte da criação desses formatos, Peter Deutsch escreveu a especificação Deflate e a publicou sob o nome Internet RFC 1951 em maio de 1996. Acabou sendo uma descrição mais acessível em comparação com a Nota de Aplicação PKZip original.Hoje, o zlib é usado em qualquer lugar. Talvez ele agora seja responsável por compactar esta página em um servidor da Web e descompactá-la no seu navegador. Hoje, a maioria dos arquivos zip é compactada e descompactada usando o zlib.Winzip
Muitos dos que não encontraram o PKZip usaram o WinZip. Os usuários de PC passaram do DOS para o Windows e do PKZip para o WinZip.Tudo começou com um projeto do programador Nico Mac, que criou o software para OS / 2 no Mansfield Software Group em Storrs-Mansfield, Connecticut. Nico usou o Presentation Manager, esta é uma interface gráfica do usuário no OS / 2, e ficou chateado por ter que mudar de um gerenciador de arquivos para comandos do DOS toda vez que desejava criar arquivos Zip.O Mac escreveu um programa GUI simples que funcionava com arquivos Zip diretamente no Presentation Manager, chamado PMZip, e o lançou como shareware nos anos 90.O OS / 2 não teve êxito e o mundo dos PCs assumiu o Microsoft Windows. Em 1991, Mac decidiu aprender a escrever programas Windows, e seu primeiro projeto foi portar seu aplicativo Zip para um novo sistema operacional. Em abril de 1991, o WinZip 1.00 foi lançado . Foi distribuído como shareware com um período de teste de 21 dias e uma taxa de registro de US $ 29. Ela ficou assim:Nas primeiras versões do WinZip, o PKZip foi usado sob o capô. Porém, a partir da versão 5.0 em 1993, o código do Info-ZIP começou a ser usado para o processamento direto de arquivos Zip. A interface do usuário também evoluiu gradualmente.WinZip 6.3 no Windows 3.11 para grupos de trabalho.O WinZip foi um dos programas shareware mais populares nos anos 90. Mas, no final, perdeu relevância devido à incorporação de suporte para arquivos Zip nos sistemas operacionais. O Windows trabalha com eles como "pastas compactadas" desde 2001 (Windows XP), a biblioteca DynaZip é usada para isso.O Mac foi originalmente chamado Nico Mak Computing. Em 2000, ele foi renomeado para WinZip Computing e, por esses anos, Mack o deixou. Em 2005, a Vector Capital vendeu a empresae, no final, tornou-se propriedade da Corel , que ainda lança o WinZip como um produto.Compressão Lempel-Ziv (LZ77)
A compressão zip consiste em dois ingredientes principais: compressão Lempel-Ziv e código Huffman.Uma maneira de compactar o texto é criar uma lista de palavras ou frases comuns com a substituição de variedades dessas palavras no texto por links de dicionário. Por exemplo, a palavra longa "compressão" no texto de origem pode ser representada como # 1234, em que 1234 se refere à posição da palavra na lista. Isso é chamado de compactação de dicionário .Mas, do ponto de vista da compactação universal, esse método tem várias desvantagens. Primeiro, o que exatamente deve entrar no dicionário? Os dados de origem podem estar em diferentes idiomas, até podem ser textos legíveis por humanos. E se o dicionário não for previamente acordado entre compactação e descompactação, ele deverá ser armazenado e transferido junto com os dados compactados, o que reduz os benefícios da compactação.Uma solução elegante para esse problema é usar os próprios dados de origem como um dicionário. Em 1977, um algoritmo universal para compactação de dados seqüenciais , Jacob Ziv e Abraham Lempel (que trabalhou na Technion), propuseram um esquema de compactação no qual os dados de origem são apresentados como uma sequência de trigêmeos:(, , )
onde
eles
formam um link para trás para a sequência de caracteres que você deseja copiar da posição anterior no texto original e
esse é o próximo caractere nos dados gerados.Abraham Lempel e Jacob Ziv.Considere as seguintes linhas:It was the best of times,
it was the worst of times,
Na segunda linha, a sequência "t era w" pode ser representada como (26, 10, w), pois é recriada copiando 10 caracteres da posição de 26 caracteres para a letra "w". Para caracteres que ainda não apareceram, são usados backlinks de comprimento zero. Por exemplo, o inicial "I" pode ser representado como (0, 0, I).Esse esquema é chamado de compactação Lempel-Ziv ou compactação LZ77. No entanto, em implementações práticas do algoritmo, parte do trigêmeo geralmente não é usada
. Em vez disso, os caracteres são gerados individualmente e os pares (
,
) são usados para backlinks (essa opção é chamada de compactação LZSS ). Como os literais e os backlinks são codificados é um problema separado, consideraremos abaixo quando analisarmos o algoritmoO Deflate .Esse texto:It was the best of times,
it was the worst of times,
it was the age of wisdom,
it was the age of foolishness,
it was the epoch of belief,
it was the epoch of incredulity,
it was the season of Light,
it was the season of Darkness,
it was the spring of hope,
it was the winter of despair,
we had everything before us,
we had nothing before us,
we were all going direct to Heaven,
we were all going direct the other way
Você pode compactar nisto:It was the best of times,
i(26,10)wor(27,24)age(25,4)wisdom(26,20)
foolishnes(57,14)epoch(33,4)belief(28,22)incredulity
(33,13)season(34,4)Light(28,23)Dark(120,17)
spring(31,4)hope(231,14)inter(27,4)despair,
we had everyth(57,4)before us(29,9)no(26,20)
we(12,3)all go(29,4)direct to Heaven
(36,28)(139,3)(83,3)(138,3)way
Uma das propriedades importantes dos backlinks é que eles podem se sobrepor. Isso acontece quando o comprimento é maior que a distância. Por exemplo:Fa-la-la-la-la
Você pode compactar para:Fa-la(3,9)
Isso pode lhe parecer estranho, mas o método funciona: depois que os bytes dos três primeiros "-la" são copiados, a cópia continua usando os bytes gerados recentemente.De fato, esse é um tipo de codificação de comprimentos de séries , em que parte dos dados é copiada repetidamente para obter o comprimento desejado.Um exemplo interativo do uso da compressão Lempel-Ziv para letras é mostrado em um artigo de Colin Morris As letras pop estão ficando mais repetitivas? .A seguir, é apresentado um exemplo de cópia de backlinks em C. Observe que, devido a uma possível sobreposição, não podemos usar memcpy
ou memmove
.
static inline void lz77_output_backref(uint8_t *dst, size_t dst_pos,
size_t dist, size_t len)
{
size_t i;
assert(dist <= dst_pos && "cannot reference before beginning of dst");
for (i = 0; i < len; i++) {
dst[dst_pos] = dst[dst_pos - dist];
dst_pos++;
}
}
É fácil gerar literais, mas, para completar, usaremos uma função auxiliar:
static inline void lz77_output_lit(uint8_t *dst, size_t dst_pos, uint8_t lit)
{
dst[dst_pos] = lit;
}
Observe que o chamador dessa função deve garantir que haja dst
espaço suficiente para os dados gerados e que o backlink não acesse a posição antes do início do buffer.É difícil não gerar dados usando backlinks durante a descompactação, mas criá-los primeiro ao compactar os dados de origem. Isso pode ser feito de maneiras diferentes, mas usaremos o método baseado em tabelas de hash do zlib, proposto na RFC 1951.Usaremos uma tabela de hash com as posições dos prefixos de três caracteres que foram encontrados anteriormente na linha (backlinks mais curtos não trazem nenhum benefício). Deflate permite backlinks com os 32.768 caracteres anteriores - isso é chamado de janela. Isso fornece compactação de fluxo contínuo: os dados de entrada são processados um pouco de cada vez, desde que a janela com os últimos bytes seja armazenada na memória. No entanto, nossa implementação assume que todos os dados de entrada estão disponíveis para nós e que podemos processá-los de uma só vez. Isso permite que você se concentre na compactação e não na contabilidade, o que é necessário para o processamento do fluxo.Usaremos duas matrizes: in head
contém o valor de hash do prefixo de três caracteres para a posição na entrada e in prev
contém a posição da posição anterior com esse valor de hash. De fato, head[h]
esse é o cabeçalho de uma lista vinculada de posições de prefixo com um hash h
e prev[x]
recebe o elemento que precede x
a lista.#define LZ_WND_SIZE 32768
#define LZ_MAX_LEN 258
#define HASH_SIZE 15
#define NO_POS SIZE_MAX
bool lz77_compress(const uint8_t *src, size_t len,
bool (*lit_callback)(uint8_t lit, void *aux),
bool (*backref_callback)(size_t dist, size_t len, void *aux),
void *aux)
{
size_t head[1U << HASH_SIZE];
size_t prev[LZ_WND_SIZE];
uint16_t h;
size_t i, j, dist;
size_t match_len, match_pos;
size_t prev_match_len, prev_match_pos;
for (i = 0; i < sizeof(head) / sizeof(head[0]); i++) {
head[i] = NO_POS;
}
Para inserir uma nova posição de string na tabela de hash prev
, ela é atualizada para indicar a anterior head
e, em seguida, é atualizada head
:static void insert_hash(uint16_t hash, size_t pos, size_t *head, size_t *prev)
{
prev[pos % LZ_WND_SIZE] = head[hash];
head[hash] = pos;
}
Preste atenção na operação do módulo ao indexar prev
: estamos interessados apenas nas posições que caem na janela atual.Em vez de calcular o valor do hash para cada prefixo de três caracteres do zero, usaremos um hash de anel e o atualizaremos constantemente para que apenas os três últimos caracteres sejam refletidos em seu valor:static uint16_t update_hash(uint16_t hash, uint8_t c)
{
hash <<= 5;
hash ^= c;
hash &= (1U << HASH_SIZE) - 1;
return hash;
}
O mapa de hash pode então ser usado para pesquisar com eficiência as correspondências anteriores com uma sequência, conforme mostrado abaixo. A procura de correspondências é a operação de compactação que consome mais recursos, portanto, limitaremos a profundidade da pesquisa na lista.A alteração de vários parâmetros, como a profundidade da pesquisa na lista de prefixos e a comparação lenta, conforme descrito abaixo, é uma maneira de aumentar a velocidade, reduzindo a taxa de compactação. As configurações em nosso código são selecionadas para corresponder ao nível máximo de compactação no zlib.
static size_t find_match(const uint8_t *src, size_t pos, uint16_t hash,
size_t prev_match_len, size_t max_match_len,
const size_t *head, const size_t *prev,
size_t *match_pos)
{
size_t max_match_steps = 4096;
size_t i, l;
bool found;
if (prev_match_len == 0) {
prev_match_len = 2;
}
if (prev_match_len >= max_match_len) {
return 0;
}
if (prev_match_len >= 32) {
max_match_steps /= 4;
}
found = false;
i = head[hash];
while (max_match_steps != 0) {
if (i == NO_POS) {
break;
}
assert(i < pos && "Matches should precede pos.");
if (pos - i > LZ_WND_SIZE) {
break;
}
l = cmp(src, i, pos, prev_match_len, max_match_len);
if (l != 0) {
assert(l > prev_match_len);
assert(l <= max_match_len);
found = true;
*match_pos = i;
prev_match_len = l;
if (l == max_match_len) {
return l;
}
}
i = prev[i % LZ_WND_SIZE];
max_match_steps--;
}
if (!found) {
return 0;
}
return prev_match_len;
}
static size_t cmp(const uint8_t *src, size_t i, size_t j,
size_t prev_match_len, size_t max_match_len)
{
size_t l;
assert(prev_match_len < max_match_len);
for (l = 0; l < prev_match_len + 1; l++) {
if (src[i + prev_match_len - l] !=
src[j + prev_match_len - l]) {
return 0;
}
}
assert(l == prev_match_len + 1);
for (; l < max_match_len; l++) {
if (src[i + l] != src[j + l]) {
break;
}
}
assert(l > prev_match_len);
assert(l <= max_match_len);
assert(memcmp(&src[i], &src[j], l) == 0);
return l;
}
Você pode encerrar a função com lz77_compress
este código para procurar correspondências anteriores:
h = 0;
if (len >= 2) {
h = update_hash(h, src[0]);
h = update_hash(h, src[1]);
}
prev_match_len = 0;
prev_match_pos = 0;
for (i = 0; i + 2 < len; i++) {
h = update_hash(h, src[i + 2]);
match_len = find_match(src, i, h, prev_match_len,
min(LZ_MAX_LEN, len - i), head, prev,
&match_pos);
insert_hash(h, i, head, prev);
if (prev_match_len != 0 && prev_match_len >= match_len) {
dist = (i - 1) - prev_match_pos;
if (!backref_callback(dist, prev_match_len, aux)) {
return false;
}
for (j = i + 1; j < min((i - 1) + prev_match_len,
len - 2); j++) {
h = update_hash(h, src[j + 2]);
insert_hash(h, j, head, prev);
}
i = (i - 1) + prev_match_len - 1;
prev_match_len = 0;
continue;
}
if (match_len == 0) {
assert(prev_match_len == 0);
if (!lit_callback(src[i], aux)) {
return false;
}
continue;
}
if (prev_match_len != 0) {
if (!lit_callback(src[i - 1], aux)) {
return false;
}
}
prev_match_len = match_len;
prev_match_pos = match_pos;
}
if (prev_match_len != 0) {
dist = (i - 1) - prev_match_pos;
if (!backref_callback(dist, prev_match_len, aux)) {
return false;
}
i = (i - 1) + prev_match_len;
}
for (; i < len; i++) {
if (!lit_callback(src[i], aux)) {
return false;
}
}
return true;
}
Esse código está procurando o backlink mais longo que pode ser gerado na posição atual. Porém, antes de emiti-lo, o programa decide se é possível encontrar uma correspondência ainda mais longa na próxima posição. No zlib, isso é chamado de avaliação de comparação lenta . Esse ainda é um algoritmo ganancioso : ele seleciona a correspondência mais longa, mesmo que a atual mais curta permita que você obtenha uma correspondência ainda mais longa e obtenha uma compactação mais forte.A compactação Lempel-Ziv pode funcionar rápida e lentamente. Zopfligastou muito tempo procurando backlinks ótimos para extrair porcentagens extras de compactação. Isso é útil para dados compactados uma vez e depois reutilizados, por exemplo, para informações estáticas em um servidor da web. Do outro lado da balança, estão compressores como Snappy e LZ4 , que são comparados apenas com o último prefixo de 4 bytes e são muito rápidos. Esse tipo de compactação é útil em bancos de dados e sistemas RPC nos quais o tempo gasto na compactação compensa economizando tempo ao enviar dados pela rede ou para o disco.A idéia de usar dados de origem como um dicionário é muito elegante, mas você também pode se beneficiar de um dicionário estático. Brotli é um algoritmo baseado em LZ77, mas também usa um grandedicionário estático de cadeia de caracteres, frequentemente encontrado na rede.Código LZ77 pode ser visto em lz77.h e lz77.c .Código Huffman
O segundo algoritmo de compactação Zip é o código de Huffman.O termo código neste contexto é uma referência a um sistema para apresentar dados de alguma outra forma. Nesse caso, estamos interessados no código que pode ser usado para representar com eficiência literais e backlinks gerados pelo algoritmo Lempel-Ziv.Tradicionalmente, o texto em inglês é apresentado usando o Código Padrão Americano para Intercâmbio de Informações (ASCII) . Este sistema atribui a cada caractere um número, que geralmente é armazenado em uma representação de 8 bits. Aqui estão os códigos ASCII para as letras maiúsculas do alfabeto inglês:Um byte por caractere é uma maneira conveniente de armazenar texto. Ele permite que você acesse ou modifique partes do texto com facilidade, e é sempre claro quantos bytes são necessários para armazenar N caracteres ou quantos caracteres são armazenados em N bytes. No entanto, essa não é a maneira mais eficaz em termos de espaço ocupado. Por exemplo, em inglês, a letra E é usada com mais frequência e Z é o menos usado. Portanto, em termos de volume, é mais eficiente usar uma representação de bits mais curta para E e uma representação mais longa para Z, em vez de atribuir o mesmo número de bits a cada caractere.Um código que especifica codificações de comprimentos diferentes para caracteres de origem diferentes é chamado de código de comprimento variável . O exemplo mais famoso é o código Morse., em que cada caractere é codificado com pontos e traços, originalmente transmitidos por telégrafo com pulsos curtos e longos:Uma das desvantagens do código Morse é que uma palavra de código pode ser um prefixo de outra. Por exemplo, • • - • não possui uma decodificação exclusiva: pode ser F ou ER. Isso é resolvido por pausas (três pontos de comprimento) entre as letras durante a transmissão. No entanto, seria melhor se as palavras de código não pudessem ser prefixos de outras palavras. Este código é chamado não refixed . O código ASCII de um comprimento fixo não é fixo, porque as palavras de código sempre têm o mesmo comprimento. Mas os códigos de comprimento variável também podem ser não corrigidos. Os números de telefone geralmente não são corrigidos. Antes do número de telefone de emergência 112 ser introduzido na Suécia, todos os números começando com 112 tinham que ser alterados e, nos EUA, não havia um único número de telefone começando com 911.Para minimizar o tamanho da mensagem codificada, é melhor usar um código não refixado no qual caracteres que ocorrem frequentemente têm palavras de código mais curtas. O código ideal será o que gera o menor resultado possível - a soma dos comprimentos das palavras de código, multiplicadas pela frequência de ocorrência, será o mínimo possível. Isso é chamado de código sem prefixo com redundância mínima , ou um código de Huffman , em homenagem ao inventor de um algoritmo eficiente para gerar esses códigos.Algoritmo de Huffman
Enquanto estudava materiais para escrever sua dissertação de doutorado em engenharia eletrônica no MIT, David Huffman participou de um curso sobre teoria da informação ministrado por Robert Fano. Segundo a lenda , Fano permitiu que seus alunos escolhessem: escrever o exame final ou o curso. Huffman escolheu o último e recebeu o tópico de procurar códigos sem prefixo com redundância mínima. Supõe-se que ele não sabia que o próprio Fano estava trabalhando nessa tarefa naquela época (o algoritmo Shannon-Fano foi o método mais famoso naqueles anos ). O trabalho de Huffman foi publicado em 1952, sob o título Um método para a construção de códigos de redundância mínima em 1952. E desde então, seu algoritmo tem sido amplamente utilizado.David Huffman, comunicado de imprensa da UC Santa Cruz.O algoritmo Huffman cria código não refixed com redundância mínima para o conjunto de caracteres e sua frequência de uso. O algoritmo seleciona repetidamente dois caracteres com menor probabilidade de serem encontrados nos dados de origem - digamos, X e Y - e os substitui por um caractere composto que significa “X ou Y”. A frequência de ocorrência de um símbolo composto é a soma das frequências de dois símbolos de origem. As palavras de código para X e Y podem ser quaisquer palavras de código atribuídas ao caractere composto “X ou Y” seguido de 0 ou 1 para distinguir os caracteres originais. Quando os dados de entrada são reduzidos a um caractere, o algoritmo para de funcionar ( explicação em vídeo ).Aqui está um exemplo do algoritmo trabalhando em um pequeno conjunto de caracteres:Primeira iteração do processamento:Os dois símbolos mais raros, C e D, são removidos do aparelho e substituídos por um símbolo composto cuja frequência é a soma das frequências C e D:Agora, os símbolos mais raros são B e um símbolo composto com uma frequência de 5. Eles são removidos do conjunto e substituídos por um símbolo composto com uma frequência de 9:Finalmente, A e um símbolo composto com frequência 9 são combinados em um novo símbolo com frequência 15:Todo o conjunto foi reduzido para um caractere, o processamento está completo.O algoritmo criou uma estrutura chamada árvore de Huffman . Os caracteres de entrada são folhas, e quanto maior a frequência de um caractere, mais alto ele será localizado. A partir da raiz da árvore, você pode gerar palavras de código para caracteres adicionando 0 ou 1 ao mover para a esquerda ou direita, respectivamente. Acontece assim:Nenhuma palavra de código é um prefixo para qualquer outra. Quanto mais frequentemente um símbolo ocorre, menor é a sua palavra-código.A árvore também pode ser usada para decodificação: começamos a partir da raiz e vamos para a direita ou esquerda para o valor com 0 ou 1 na frente do caractere. Por exemplo, a linha 010100 é decodificada no ABBA.Observe que o comprimento de cada palavra de código é equivalente à profundidade do nó da árvore correspondente. Como veremos na próxima parte, não precisamos de uma árvore real para atribuir palavras de código. Basta saber o tamanho das próprias palavras. Assim, o resultado de nossa implementação do algoritmo de Huffman será o comprimento das palavras de código.Para armazenar o conjunto de caracteres e encontrar com eficiência as frequências mais baixas, usaremos a estrutura de dados da pilha binária . Em particular, estamos interessados emmin-heap , como o valor mínimo deve estar no topo.
static void swap32(uint32_t *a, uint32_t *b)
{
uint32_t tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
static void minheap_down(uint32_t *heap, size_t n, size_t i)
{
size_t left, right, min;
assert(i >= 1 && i <= n && "i must be inside the heap");
while (i * 2 <= n) {
left = i * 2;
right = i * 2 + 1;
min = left;
if (right <= n && heap[right] < heap[left]) {
min = right;
}
if (heap[min] < heap[i]) {
swap32(&heap[min], &heap[i]);
i = min;
} else {
break;
}
}
}
static void minheap_heapify(uint32_t *heap, size_t n)
{
size_t i;
for (i = n / 2; i >= 1; i--) {
minheap_down(heap, n, i);
}
}
Para rastrear a frequência dos n
caracteres, usaremos vários n
elementos. Além disso, sempre que um símbolo composto é criado, queremos “vincular” ambos os símbolos de origem a ele. Portanto, cada símbolo terá um "elemento de comunicação".Para armazenar os n
elementos de pilha e n
comunicação -element, usaremos uma matriz de n * 2 + 1
elementos. Quando dois caracteres no heap são substituídos por um, usaremos o segundo elemento para salvar o link no novo caractere. Essa abordagem é baseada na implementação do Gerenciamento de Gigabytes de Witten, Moffat e Bell.Em cada nó da pilha, usaremos os 16 bits mais significativos para armazenar a frequência do símbolo e os 16 bits menos significativos para armazenar o índice do elemento de comunicação do símbolo. Devido ao uso de bits altos, a diferença de frequência será determinada pelo resultado de uma comparação de 32 bits entre dois elementos do heap.Devido a essa representação, precisamos garantir que a frequência de caracteres sempre caiba em 16 bits. Após a conclusão do algoritmo, o símbolo final composto terá a frequência de todos os símbolos combinados, ou seja, essa soma deve ser colocada em 16 bits. Nossa implementação de Deflate verificará isso processando simultaneamente até 64.535 caracteres.Símbolos com frequência zero receberão palavras de código com comprimento zero e não participarão da compilação da codificação.Se a palavra-código atingir a profundidade máxima especificada, "suavizaremos" a distribuição de frequência impondo um limite de frequência e tentaremos novamente (sim, com a ajuda goto
). Existem maneiras mais sofisticadas de fazer a codificação Huffman com profundidade limitada, mas essa é simples e eficiente.#define MAX_HUFFMAN_SYMBOLS 288
static void compute_huffman_lengths(const uint16_t *freqs, size_t n,
uint8_t max_len, uint8_t *lengths)
{
uint32_t nodes[MAX_HUFFMAN_SYMBOLS * 2 + 1], p, q;
uint16_t freq;
size_t i, h, l;
uint16_t freq_cap = UINT16_MAX;
#ifndef NDEBUG
uint32_t freq_sum = 0;
for (i = 0; i < n; i++) {
freq_sum += freqs[i];
}
assert(freq_sum <= UINT16_MAX && "Frequency sum too large!");
#endif
assert(n <= MAX_HUFFMAN_SYMBOLS);
assert((1U << max_len) >= n && "max_len must be large enough");
try_again:
h = 0;
for (i = 0; i < n; i++) {
freq = freqs[i];
if (freq == 0) {
continue;
}
if (freq > freq_cap) {
freq = freq_cap;
}
h++;
nodes[h] = ((uint32_t)freq << 16) | (uint32_t)(n + h);
}
minheap_heapify(nodes, h);
if (h < 2) {
for (i = 0; i < n; i++) {
lengths[i] = (freqs[i] == 0) ? 0 : 1;
}
return;
}
while (h > 1) {
p = nodes[1];
nodes[1] = nodes[h--];
minheap_down(nodes, h, 1);
q = nodes[1];
nodes[1] = ((p & 0xffff0000) + (q & 0xffff0000))
| (uint32_t)(h + 1);
nodes[p & 0xffff] = nodes[q & 0xffff] = (uint32_t)(h + 1);
minheap_down(nodes, h, 1);
}
h = 0;
for (i = 0; i < n; i++) {
if (freqs[i] == 0) {
lengths[i] = 0;
continue;
}
h++;
p = nodes[n + h];
l = 1;
while (p != 2) {
l++;
p = nodes[p];
}
if (l > max_len) {
assert(freq_cap != 1 && "Cannot lower freq_cap!");
freq_cap /= 2;
goto try_again;
}
assert(l <= UINT8_MAX);
lengths[i] = (uint8_t)l;
}
}
Uma alternativa elegante à opção de pilha binária é armazenar caracteres em duas filas. O primeiro contém os caracteres de origem, classificados por frequência. Quando um símbolo composto é criado, ele é adicionado secundariamente. Assim, o símbolo com a frequência mais baixa estará sempre na primeira posição de uma das filas. Essa abordagem é descrita por Jan van Leeuwen em Na construção de árvores de Huffman (1976).A codificação de Huffman é ideal para códigos sem prefixo, mas em outros casos existem métodos mais eficientes: codificação aritmética e sistemas de números assimétricos .Códigos canônicos de Huffman
No exemplo acima, criamos uma árvore Huffman:Se formos da raiz e usar 0 para o ramo esquerdo e 1 para o direito, obteremos os seguintes códigos:A decisão de usar 0 para o ramo esquerdo e 1 para o direito parece arbitrária. Se fizermos o oposto, obtemos:Podemos marcar arbitrariamente dois ramos originários de um nó com zero e um (o principal é que os rótulos sejam diferentes) e ainda assim obter o código equivalente:Embora o algoritmo Huffman forneça os comprimentos de palavras de código necessários para o código não refixed com redundância mínima, há muitas maneiras de atribuir palavras de código individuais.Dado o comprimento da palavra de código calculada pelo algoritmo de Huffman, o código canônico de Huffman atribui as palavras de código aos caracteres de uma maneira específica. Isso é útil porque permite armazenar e transmitir comprimentos de palavras de código com dados compactados: o decodificador poderá recuperar palavras de código com base em seus comprimentos. Obviamente, você pode armazenar e transmitir frequências de símbolos e executar o algoritmo Huffman no decodificador, mas isso exigirá mais trabalho e mais armazenamento do decodificador. Outra propriedade muito importante é que a estrutura dos códigos canônicos utiliza decodificação eficiente.A idéia é atribuir palavras de código aos caracteres sequencialmente, sob uma de cada vez. A primeira palavra de código é 0. A próxima será uma palavra com um comprimento da palavra anterior + 1. A primeira palavra com um comprimento de N é composta da última palavra de comprimento N-1, adicionando uma (para obter uma nova palavra de código) e deslocando um passo para a esquerda (para aumentar o comprimento).Na terminologia da árvore Hoffman, as palavras de código são atribuídas seqüencialmente às folhas na ordem da esquerda para a direita, um nível de cada vez, deslocando-se para a esquerda ao passar para o próximo nível.No nosso exemplo ABCD, o algoritmo Huffman atribuiu palavras de código com comprimentos de 1, 2, 3 e 3. A primeira palavra é 0. Essa também é a última palavra de comprimento 1. No comprimento 2, usamos 0 e adicionamos 1 para obter o próximo código, que se tornará o prefixo dos códigos de dois bits. , desloque-se para a esquerda e obtenha 10. Esta é agora a última palavra do comprimento 2. Para obter o comprimento 3, adicionamos 1 e o deslocamento: 110. Para obter a próxima palavra do comprimento 3, adicionamos 1: 111.A implementação do gerador de código canônico é mostrada abaixo. Observe que o algoritmo Deflate espera que as palavras de código sejam geradas com base no princípio LSB-first (primeiro, o bit menos significativo). Ou seja, o primeiro bit da palavra-código deve ser armazenado no bit menos significativo. Isso significa que precisamos alterar a ordem dos bits, por exemplo, usando a tabela de pesquisa.#define MAX_HUFFMAN_BITS 15
static void compute_canonical_code(uint16_t *codewords, const uint8_t *lengths,
size_t n)
{
size_t i;
uint16_t count[MAX_HUFFMAN_BITS + 1] = {0};
uint16_t code[MAX_HUFFMAN_BITS + 1];
int l;
for (i = 0; i < n; i++) {
count[lengths[i]]++;
}
count[0] = 0;
code[0] = 0;
for (l = 1; l <= MAX_HUFFMAN_BITS; l++) {
code[l] = (uint16_t)((code[l - 1] + count[l - 1]) << 1);
}
for (i = 0; i < n; i++) {
l = lengths[i];
if (l == 0) {
continue;
}
codewords[i] = reverse16(code[l]++, l);
}
}
static inline uint16_t reverse16(uint16_t x, int n)
{
uint16_t lo, hi;
uint16_t reversed;
assert(n > 0);
assert(n <= 16);
lo = x & 0xff;
hi = x >> 8;
reversed = (uint16_t)((reverse8_tbl[lo] << 8) | reverse8_tbl[hi]);
return reversed >> (16 - n);
}
Agora junte tudo e escreva o código de inicialização do codificador:typedef struct huffman_encoder_t huffman_encoder_t;
struct huffman_encoder_t {
uint16_t codewords[MAX_HUFFMAN_SYMBOLS];
uint8_t lengths[MAX_HUFFMAN_SYMBOLS];
};
void huffman_encoder_init(huffman_encoder_t *e, const uint16_t *freqs, size_t n,
uint8_t max_codeword_len)
{
assert(n <= MAX_HUFFMAN_SYMBOLS);
assert(max_codeword_len <= MAX_HUFFMAN_BITS);
compute_huffman_lengths(freqs, n, max_codeword_len, e->lengths);
compute_canonical_code(e->codewords, e->lengths, n);
}
Também criamos uma função para configurar o codificador usando os comprimentos de código já calculados:
void huffman_encoder_init2(huffman_encoder_t *e, const uint8_t *lengths,
size_t n)
{
size_t i;
for (i = 0; i < n; i++) {
e->lengths[i] = lengths[i];
}
compute_canonical_code(e->codewords, e->lengths, n);
}
Decodificação eficiente de Huffman
A maneira mais fácil de decodificar Huffman é atravessar a árvore a partir da raiz, lendo um pouco de entrada de cada vez e decidindo qual ramo seguir, esquerda ou direita. Quando um nó folha é atingido, é um caractere decodificado.Este método é frequentemente ensinado em universidades e livros. É simples e elegante, mas o processamento de um bit por vez é muito lento. É muito mais rápido decodificar usando a tabela de pesquisa. Para o exemplo acima, no qual o comprimento máximo da palavra de código é três bits, você pode usar a seguinte tabela:Embora haja apenas quatro caracteres, precisamos de uma tabela com oito entradas para cobrir todas as combinações possíveis de três bits. Símbolos com palavras de código menores que três bits têm várias entradas na tabela. Por exemplo, a palavra 10 foi "suplementada" com 10 0 e 10 1 para cobrir todas as combinações de três bits começando com 10.Para decodificar dessa maneira, você precisa indexar na tabela os três bits de entrada a seguir e encontrar imediatamente o caractere correspondente e o comprimento de sua palavra de código. O comprimento é importante porque, apesar de observar os próximos três bits, precisamos obter o mesmo número de bits de entrada que o comprimento da palavra de código.O método baseado em tabela de pesquisa funciona muito rapidamente, mas tem uma desvantagem: o tamanho da tabela dobra a cada bit adicional no comprimento da palavra de código. Ou seja, a construção da tabela diminui exponencialmente e, se ela parar de caber no cache do processador, o método começará a funcionar lentamente.Por esse motivo, a tabela de pesquisa geralmente é usada apenas para palavras de código não maiores que um determinado comprimento. E para palavras mais longas, adote uma abordagem diferente. Assim como a codificação Huffman atribui palavras de código mais curtas a caracteres mais freqüentes, o uso de uma tabela de pesquisa para palavras de código curtas é, em muitos casos, uma excelente otimização.Em zlibvários níveis de tabelas de pesquisa são usados. Se a palavra-código for muito longa para a primeira tabela, a pesquisa irá para a tabela secundária para indexar os bits restantes.Mas existe outro método muito elegante, baseado nas propriedades dos códigos canônicos de Huffman. É descrito em Sobre a implementação de códigos de prefixo mínimo de redundância (Moffat e Turpin, 1997) e também é explicado no The Lost Huffman Paper de Charles Bloom.Vamos pegar as palavras-código da versão canônica: 0, 10, 110, 111. Rastrearemos as primeiras palavras-código de cada comprimento, bem como o número de cada palavra-código na sequência geral - “índice de símbolos”.Como as palavras de código são atribuídas seqüencialmente, se soubermos o número de bits, podemos encontrar na tabela acima o símbolo que esses bits representam. Por exemplo, para três bits 111, vemos que esse é um deslocamento de um da primeira palavra de código desse comprimento (110). O primeiro índice de caracteres desse comprimento é 3 e um deslocamento de um fornece um índice de 4. Outra tabela compara o índice de caracteres com o caractere:sym_idx = d->first_symbol[len] + (bits - d->first_code[len]);
sym = d->syms[sym_idx];
Um pouco de otimização: em vez de armazenar separadamente o primeiro índice de caracteres e a primeira palavra de código, podemos armazenar o primeiro índice na tabela menos a primeira palavra de código:sym_idx = d->offset_first_sym_idx[len] + bits;
sym = d->syms[sym_idx];
Para entender quantos bits precisam ser estimados, usamos novamente a propriedade de sequência de código. No nosso exemplo, todas as palavras de código de um bit válidas são estritamente menores que 1, dois bits - estritamente menores que 11, três bits - menores que 1000 (de fato, verdade para todos os valores de três bits). Em outras palavras, a palavra de código de N bits válida deve ser estritamente menor que a primeira palavra de código de N bits mais o número de palavras de código de N bits. Além disso, podemos mudar esses limites para a esquerda, para que todos tenham três bits de largura. Vamos chamá-lo de bits restritivos para cada um dos comprimentos das palavras de código:O limitador do comprimento 3 ultrapassou os 4 bits, mas isso significa apenas que qualquer palavra de três bits será suficiente.Podemos pesquisar entre os dados de entrada de três bits e comparar com os bits restritivos para entender quanto tempo nossa palavra de código é. Após a conclusão, alteramos os bits de entrada, apenas para calcular o número correto e, em seguida, localizamos o índice de caracteres:for (len = 1; len <= 3; len++) {
if (bits < d->sentinel_bits[len]) {
bits >>= 3 - len;
sym_idx = d->offset_first_sym_idx[len] + bits;
}
}
A complexidade de tempo do processo é linear em relação ao número de bits nas palavras de código, mas o local é gasto com eficiência, apenas o carregamento e a comparação são necessários a cada etapa e, como as palavras de código mais curtas são mais comuns, o método permite otimizar a compactação em muitas situações.Código completo do decodificador:#define HUFFMAN_LOOKUP_TABLE_BITS 8
typedef struct huffman_decoder_t huffman_decoder_t;
struct huffman_decoder_t {
struct {
uint16_t sym : 9;
uint16_t len : 7;
} table[1U << HUFFMAN_LOOKUP_TABLE_BITS];
uint16_t sentinel_bits[MAX_HUFFMAN_BITS + 1];
uint16_t offset_first_sym_idx[MAX_HUFFMAN_BITS + 1];
uint16_t syms[MAX_HUFFMAN_SYMBOLS];
#ifndef NDEBUG
size_t num_syms;
#endif
};
static inline uint64_t lsb(uint64_t x, int n)
{
assert(n >= 0 && n <= 63);
return x & (((uint64_t)1 << n) - 1);
}
static inline int huffman_decode(const huffman_decoder_t *d, uint16_t bits,
size_t *num_used_bits)
{
uint64_t lookup_bits;
size_t l;
size_t sym_idx;
lookup_bits = lsb(bits, HUFFMAN_LOOKUP_TABLE_BITS);
assert(lookup_bits < sizeof(d->table) / sizeof(d->table[0]));
if (d->table[lookup_bits].len != 0) {
assert(d->table[lookup_bits].len <= HUFFMAN_LOOKUP_TABLE_BITS);
assert(d->table[lookup_bits].sym < d->num_syms);
*num_used_bits = d->table[lookup_bits].len;
return d->table[lookup_bits].sym;
}
bits = reverse16(bits, MAX_HUFFMAN_BITS);
for (l = HUFFMAN_LOOKUP_TABLE_BITS + 1; l <= MAX_HUFFMAN_BITS; l++) {
if (bits < d->sentinel_bits[l]) {
bits >>= MAX_HUFFMAN_BITS - l;
sym_idx = (uint16_t)(d->offset_first_sym_idx[l] + bits);
assert(sym_idx < d->num_syms);
*num_used_bits = l;
return d->syms[sym_idx];
}
}
*num_used_bits = 0;
return -1;
}
Para configurar o decodificador, calcularemos previamente os códigos canônicos, como para huffman_encoder_init , e preencheremos diferentes tabelas:
bool huffman_decoder_init(huffman_decoder_t *d, const uint8_t *lengths,
size_t n)
{
size_t i;
uint16_t count[MAX_HUFFMAN_BITS + 1] = {0};
uint16_t code[MAX_HUFFMAN_BITS + 1];
uint32_t s;
uint16_t sym_idx[MAX_HUFFMAN_BITS + 1];
int l;
#ifndef NDEBUG
assert(n <= MAX_HUFFMAN_SYMBOLS);
d->num_syms = n;
#endif
for (i = 0; i < sizeof(d->table) / sizeof(d->table[0]); i++) {
d->table[i].len = 0;
}
for (i = 0; i < n; i++) {
assert(lengths[i] <= MAX_HUFFMAN_BITS);
count[lengths[i]]++;
}
count[0] = 0;
code[0] = 0;
sym_idx[0] = 0;
for (l = 1; l <= MAX_HUFFMAN_BITS; l++) {
code[l] = (uint16_t)((code[l - 1] + count[l - 1]) << 1);
if (count[l] != 0 && code[l] + count[l] - 1 > (1U << l) - 1) {
return false;
}
s = (uint32_t)((code[l] + count[l]) << (MAX_HUFFMAN_BITS - l));
d->sentinel_bits[l] = (uint16_t)s;
assert(d->sentinel_bits[l] == s && "No overflow.");
sym_idx[l] = sym_idx[l - 1] + count[l - 1];
d->offset_first_sym_idx[l] = sym_idx[l] - code[l];
}
for (i = 0; i < n; i++) {
l = lengths[i];
if (l == 0) {
continue;
}
d->syms[sym_idx[l]] = (uint16_t)i;
sym_idx[l]++;
if (l <= HUFFMAN_LOOKUP_TABLE_BITS) {
table_insert(d, i, l, code[l]);
code[l]++;
}
}
return true;
}
static void table_insert(huffman_decoder_t *d, size_t sym, int len,
uint16_t codeword)
{
int pad_len;
uint16_t padding, index;
assert(len <= HUFFMAN_LOOKUP_TABLE_BITS);
codeword = reverse16(codeword, len);
pad_len = HUFFMAN_LOOKUP_TABLE_BITS - len;
for (padding = 0; padding < (1U << pad_len); padding++) {
index = (uint16_t)(codeword | (padding << len));
d->table[index].sym = (uint16_t)sym;
d->table[index].len = (uint16_t)len;
assert(d->table[index].sym == sym && "Fits in bitfield.");
assert(d->table[index].len == len && "Fits in bitfield.");
}
}
Desinflar
O algoritmo de deflação, introduzido no PKZip 2.04c em 1993, é um método de compactação padrão nos arquivos Zip modernos. Também é usado em gzip, PNG e em muitos outros formatos. Ele usa uma combinação de compactação LZ77 e codificação Huffman, que discutiremos e implementaremos nesta seção.Antes de Deflate, o PKZip usava os métodos de compactação Encolher, Reduzir e Implodir. Hoje eles são raros, apesar de o Deflate ainda estar em uso por algum tempo, porque consumiram menos memória. Mas nós não os consideraremos.Fluxos de bits
Deflate armazena palavras de código Huffman em um fluxo de bits de acordo com o princípio LSB-first. Isso significa que o primeiro bit do fluxo é armazenado no bit menos significativo do primeiro byte.Considere um fluxo de bits (leia da esquerda para a direita) 1-0-0-1-1. Quando é armazenado de acordo com o princípio LSB-first, o valor do byte se torna 0b00011001 (binário) ou 0x19 (hexadecimal). Pode parecer que o fluxo é simplesmente representado de trás para frente (em certo sentido), mas a vantagem é que é mais fácil obter os primeiros N bits de uma palavra de computador: simplesmente ocultamos os N bits menos significativos.Estes procedimentos são retirados do bitstream.h :
typedef struct istream_t istream_t;
struct istream_t {
const uint8_t *src;
const uint8_t *end;
size_t bitpos;
size_t bitpos_end;
};
static inline void istream_init(istream_t *is, const uint8_t *src, size_t n)
{
is->src = src;
is->end = src + n;
is->bitpos = 0;
is->bitpos_end = n * 8;
}
Nosso decodificador Huffman precisa observar os seguintes bits no fluxo (bits suficientes para a palavra de código mais longa possível) e continuar o fluxo pelo número de bits usado pelo símbolo decodificado:#define ISTREAM_MIN_BITS (64 - 7)
static inline uint64_t istream_bits(const istream_t *is)
{
const uint8_t *next;
uint64_t bits;
int i;
next = is->src + (is->bitpos / 8);
assert(next <= is->end && "Cannot read past end of stream.");
if (is->end - next >= 8) {
bits = read64le(next);
} else {
bits = 0;
for (i = 0; i < is->end - next; i++) {
bits |= (uint64_t)next[i] << (i * 8);
}
}
return bits >> (is->bitpos % 8);
}
static inline bool istream_advance(istream_t *is, size_t n) {
if (is->bitpos + n > is->bitpos_end) {
return false;
}
is->bitpos += n;
return true;
}
O ponto principal é que, em máquinas de 64 bits, istream_bits
você geralmente pode executar como uma instrução de inicialização única e alguma aritmética, considerando que os elementos da estrutura istream_t
estão em registros. O read64le é implementado em bits.h (os compiladores modernos o convertem em um único download de 64 bits usando o princípio little-endian):
static inline uint64_t read64le(const uint8_t *p)
{
return ((uint64_t)p[0] << 0) |
((uint64_t)p[1] << 8) |
((uint64_t)p[2] << 16) |
((uint64_t)p[3] << 24) |
((uint64_t)p[4] << 32) |
((uint64_t)p[5] << 40) |
((uint64_t)p[6] << 48) |
((uint64_t)p[7] << 56);
}
Também precisamos de uma função para continuar o fluxo de bits até a borda do próximo byte:
static inline size_t round_up(size_t x, size_t m)
{
assert((m & (m - 1)) == 0 && "m must be a power of two");
return (x + m - 1) & (size_t)(-m);
}
static inline const uint8_t *istream_byte_align(istream_t *is)
{
const uint8_t *byte;
assert(is->bitpos <= is->bitpos_end && "Not past end of stream.");
is->bitpos = round_up(is->bitpos, 8);
byte = is->src + is->bitpos / 8;
assert(byte <= is->end);
return byte;
}
Para um fluxo de bits de saída, escrevemos bits usando um processo de leitura-modificação-gravação. No caso rápido, você pode escrever um pouco usando uma leitura de 64 bits, algum tipo de operação de bits e gravação de 64 bits.
typedef struct ostream_t ostream_t;
struct ostream_t {
uint8_t *dst;
uint8_t *end;
size_t bitpos;
size_t bitpos_end;
};
static inline void ostream_init(ostream_t *os, uint8_t *dst, size_t n)
{
os->dst = dst;
os->end = dst + n;
os->bitpos = 0;
os->bitpos_end = n * 8;
}
static inline size_t ostream_bit_pos(const ostream_t *os)
{
return os->bitpos;
}
static inline size_t ostream_bytes_written(ostream_t *os)
{
return round_up(os->bitpos, 8) / 8;
}
static inline bool ostream_write(ostream_t *os, uint64_t bits, size_t n)
{
uint8_t *p;
uint64_t x;
int shift, i;
assert(n <= 57);
assert(bits <= ((uint64_t)1 << n) - 1 && "Must fit in n bits.");
if (os->bitpos_end - os->bitpos < n) {
return false;
}
p = &os->dst[os->bitpos / 8];
shift = os->bitpos % 8;
if (os->end - p >= 8) {
x = read64le(p);
x = lsb(x, shift);
x |= bits << shift;
write64le(p, x);
} else {
x = 0;
for (i = 0; i < os->end - p; i++) {
x |= (uint64_t)p[i] << (i * 8);
}
x = lsb(x, shift);
x |= bits << shift;
for (i = 0; i < os->end - p; i++) {
p[i] = (uint8_t)(x >> (i * 8));
}
}
os->bitpos += n;
return true;
}
static inline void write64le(uint8_t *dst, uint64_t x)
{
dst[0] = (uint8_t)(x >> 0);
dst[1] = (uint8_t)(x >> 8);
dst[2] = (uint8_t)(x >> 16);
dst[3] = (uint8_t)(x >> 24);
dst[4] = (uint8_t)(x >> 32);
dst[5] = (uint8_t)(x >> 40);
dst[6] = (uint8_t)(x >> 48);
dst[7] = (uint8_t)(x >> 56);
}
Também precisamos escrever bytes com eficiência no fluxo. Obviamente, você pode executar gravações de 8 bits repetidamente, mas será muito mais rápido usar memcpy
:
static inline bool ostream_write_bytes_aligned(ostream_t *os,
const uint8_t *src,
size_t n)
{
if (os->bitpos_end - round_up(os->bitpos, 8) < n * 8) {
return false;
}
os->bitpos = round_up(os->bitpos, 8);
memcpy(&os->dst[os->bitpos / 8], src, n);
os->bitpos += n * 8;
return true;
}
Desembalar (Inflação)
Como o algoritmo de compactação é chamado Deflate - sopra e extrai ar de algo - o processo de desembalagem às vezes é chamado de inflação . Se você primeiro estudar esse processo, entenderemos como o formato funciona. Você pode ver o código na primeira parte do deflate.h e deflate.c , bits.h , tables.h e tables.c (gerado usando generate_tables.c ).Os dados compactados usando Deflate são armazenados como uma série de blocos.. Cada bloco começa com um cabeçalho de 3 bits, no qual o primeiro bit (menos significativo) é definido se esse for o bloco final da série e os outros dois bits indicam seu tipo.Existem três tipos de blocos: não compactado (0), compactado usando códigos Huffman fixos (1) e compactado usando códigos Huffman "dinâmicos" (2).Esse código executa a descompactação usando funções auxiliares para diferentes tipos de blocos, que serão implementados posteriormente:typedef enum {
HWINF_OK,
HWINF_FULL,
HWINF_ERR
} inf_stat_t;
inf_stat_t hwinflate(const uint8_t *src, size_t src_len, size_t *src_used,
uint8_t *dst, size_t dst_cap, size_t *dst_used)
{
istream_t is;
size_t dst_pos;
uint64_t bits;
bool bfinal;
inf_stat_t s;
istream_init(&is, src, src_len);
dst_pos = 0;
do {
bits = istream_bits(&is);
if (!istream_advance(&is, 3)) {
return HWINF_ERR;
}
bfinal = bits & 1;
bits >>= 1;
switch (lsb(bits, 2)) {
case 0:
s = inf_noncomp_block(&is, dst, dst_cap, &dst_pos);
break;
case 1:
s = inf_fixed_block(&is, dst, dst_cap, &dst_pos);
break;
case 2:
s = inf_dyn_block(&is, dst, dst_cap, &dst_pos);
break;
default:
return HWINF_ERR;
}
if (s != HWINF_OK) {
return s;
}
} while (!bfinal);
*src_used = (size_t)(istream_byte_align(&is) - src);
assert(dst_pos <= dst_cap);
*dst_used = dst_pos;
return HWINF_OK;
}
Blocos de desinflar descomprimidos
Estes são blocos "armazenados", o tipo mais simples. Começa com o próximo limite de 8 bits do fluxo de bits com uma palavra de 16 bits (len) indicando o comprimento do bloco. Atrás, há outra palavra de 16 bits (nlen), que complementa (a ordem dos bits é invertida) das palavras len. Supõe-se que o nlen atue como uma soma de verificação simples: se o arquivo estiver danificado, os valores provavelmente não serão complementares e o programa poderá detectar um erro.Depois de len e nlen são dados não compactados. Como o comprimento do bloco é um valor de 16 bits, o tamanho dos dados é limitado a 65.535 bytes.static inf_stat_t inf_noncomp_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
const uint8_t *p;
uint16_t len, nlen;
p = istream_byte_align(is);
if (!istream_advance(is, 32)) {
return HWINF_ERR;
}
len = read16le(p);
nlen = read16le(p + 2);
p += 4;
if (nlen != (uint16_t)~len) {
return HWINF_ERR;
}
if (!istream_advance(is, len * 8)) {
return HWINF_ERR;
}
if (dst_cap - *dst_pos < len) {
return HWINF_FULL;
}
memcpy(&dst[*dst_pos], p, len);
*dst_pos += len;
return HWINF_OK;
}
Desinflar blocos usando códigos fixos de Huffman
Os blocos de Compressed Deflate usam o código Huffman para representar uma sequência de literais LZ77. Backlinks são quebrados usando marcadores de final de bloco. Para literais, comprimentos de backlink e marcadores, o código litlen Huffman é usado . E para distâncias de backlink, o código dist é usado .Litlen codifica valores no intervalo de 0 a 285. Os valores 0-255 são usados para bytes literais, 256 é o marcador de fim de bloco e 257-285 são usados para comprimentos de backlink.Backlinks têm de 3 a 256 bytes de comprimento. O valor Litlen determina o comprimento base ao qual zero ou mais bits adicionais são adicionados a partir do fluxo para obter o comprimento total de acordo com a tabela abaixo. Por exemplo, um valor litlen de 269 significa um comprimento base de 19 e dois bits extras. A adição de dois bits do fluxo fornece o comprimento final de 19 a 22.Observe que um valor de litlen de 284 mais 5 bits extras pode representar comprimentos de 227 a 258; no entanto, a especificação afirma que o comprimento 258 - o comprimento máximo do backlink - deve ser representado usando um valor de litlen separado. Isso deve reduzir a codificação em situações em que o comprimento máximo é frequentemente encontrado.O descompressor usa a tabela para obter o comprimento base e bits adicionais do valor litlen (menos 257):
struct litlen_tbl_t {
uint16_t base_len : 9;
uint16_t ebits : 7;
};
const struct litlen_tbl_t litlen_tbl[29] = {
{ 3, 0 },
{ 4, 0 },
...
{ 227, 5 },
{ 258, 0 }
};
O código litlen fixo de Huffman é canônico e usa os seguintes comprimentos de palavras de código (286–287 não são valores litlen válidos, mas estão envolvidos na geração de código):O descompressor armazena esses comprimentos em uma tabela conveniente para transmissão para huffman_decoder_init
:const uint8_t fixed_litlen_lengths[288] = {
8,
8,
...
8,
};
As distâncias do backlink variam de 1 a 32.768. Elas são codificadas usando um esquema semelhante a um esquema de codificação de comprimento. O código Huffman dist codifica valores de 0 a 29, cada um dos quais corresponde ao comprimento base, ao qual bits adicionais são adicionados para obter a distância final:O código fixo dist de Huffman é canônico. Todas as palavras de código têm 5 bits. É simples, o descompressor armazena os códigos em uma tabela que pode ser usada com huffman_decoder_init
(os valores dist 30–31 não estão corretos. É indicado que eles estão envolvidos na geração dos códigos Huffman, mas na verdade não têm efeito):const uint8_t fixed_dist_lengths[32] = {
5,
5,
...
5,
};
Código de descompactação ou descompactação - deflate o bloco usando códigos fixos de Huffman:static inf_stat_t inf_fixed_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
huffman_decoder_t litlen_dec, dist_dec;
huffman_decoder_init(&litlen_dec, fixed_litlen_lengths,
sizeof(fixed_litlen_lengths) /
sizeof(fixed_litlen_lengths[0]));
huffman_decoder_init(&dist_dec, fixed_dist_lengths,
sizeof(fixed_dist_lengths) /
sizeof(fixed_dist_lengths[0]));
return inf_block(is, dst, dst_cap, dst_pos, &litlen_dec, &dist_dec);
}
#define LITLEN_EOB 256
#define LITLEN_MAX 285
#define LITLEN_TBL_OFFSET 257
#define MIN_LEN 3
#define MAX_LEN 258
#define DISTSYM_MAX 29
#define MIN_DISTANCE 1
#define MAX_DISTANCE 32768
static inf_stat_t inf_block(istream_t *is, uint8_t *dst, size_t dst_cap,
size_t *dst_pos,
const huffman_decoder_t *litlen_dec,
const huffman_decoder_t *dist_dec)
{
uint64_t bits;
size_t used, used_tot, dist, len;
int litlen, distsym;
uint16_t ebits;
while (true) {
bits = istream_bits(is);
litlen = huffman_decode(litlen_dec, (uint16_t)bits, &used);
bits >>= used;
used_tot = used;
if (litlen < 0 || litlen > LITLEN_MAX) {
return HWINF_ERR;
} else if (litlen <= UINT8_MAX) {
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
if (*dst_pos == dst_cap) {
return HWINF_FULL;
}
lz77_output_lit(dst, (*dst_pos)++, (uint8_t)litlen);
continue;
} else if (litlen == LITLEN_EOB) {
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
return HWINF_OK;
}
assert(litlen >= LITLEN_TBL_OFFSET && litlen <= LITLEN_MAX);
len = litlen_tbl[litlen - LITLEN_TBL_OFFSET].base_len;
ebits = litlen_tbl[litlen - LITLEN_TBL_OFFSET].ebits;
if (ebits != 0) {
len += lsb(bits, ebits);
bits >>= ebits;
used_tot += ebits;
}
assert(len >= MIN_LEN && len <= MAX_LEN);
distsym = huffman_decode(dist_dec, (uint16_t)bits, &used);
bits >>= used;
used_tot += used;
if (distsym < 0 || distsym > DISTSYM_MAX) {
return HWINF_ERR;
}
dist = dist_tbl[distsym].base_dist;
ebits = dist_tbl[distsym].ebits;
if (ebits != 0) {
dist += lsb(bits, ebits);
bits >>= ebits;
used_tot += ebits;
}
assert(dist >= MIN_DISTANCE && dist <= MAX_DISTANCE);
assert(used_tot <= ISTREAM_MIN_BITS);
if (!istream_advance(is, used_tot)) {
return HWINF_ERR;
}
if (dist > *dst_pos) {
return HWINF_ERR;
}
if (round_up(len, 8) <= dst_cap - *dst_pos) {
output_backref64(dst, *dst_pos, dist, len);
} else if (len <= dst_cap - *dst_pos) {
lz77_output_backref(dst, *dst_pos, dist, len);
} else {
return HWINF_FULL;
}
(*dst_pos) += len;
}
}
Preste atenção a essa otimização: quando não há espaço suficiente no buffer de saída, emitimos backlinks usando a função abaixo, que copia 64 bits por vez. Isso é "confuso" no sentido de que geralmente copia alguns bytes extras (até o próximo múltiplo de 8). Mas funciona muito mais rápido lz77_output_backref
, porque requer iterações menos cíclicas e acessos à memória. De fato, os backlinks curtos agora serão processados em uma iteração, o que é muito bom para prever ramificações.
static void output_backref64(uint8_t *dst, size_t dst_pos, size_t dist,
size_t len)
{
size_t i;
uint64_t tmp;
assert(len > 0);
assert(dist <= dst_pos && "cannot reference before beginning of dst");
if (len > dist) {
lz77_output_backref(dst, dst_pos, dist, len);
return;
}
i = 0;
do {
memcpy(&tmp, &dst[dst_pos - dist + i], 8);
memcpy(&dst[dst_pos + i], &tmp, 8);
i += 8;
} while (i < len);
}
Desinflar blocos usando códigos Huffman dinâmicos
Deflate blocos usando códigos dinâmicos de Huffman funcionam da mesma maneira como descrito acima. Mas, em vez dos códigos predefinidos para litlen e dist, eles usam os códigos armazenados no próprio fluxo Deflate no início do bloco. O nome provavelmente não teve êxito, pois os códigos que mudam durante a codificação também são chamados de códigos dinâmicos de Huffman - essa é a codificação adaptativa de Huffman . Os códigos descritos aqui não têm nada a ver com esse procedimento. Eles são dinâmicos apenas no sentido de que blocos diferentes podem usar códigos diferentes.Gerar litlen dinâmico e códigos dist é a parte mais difícil do formato Deflate. Porém, assim que os códigos são gerados, a descompressão é executada da mesma maneira descrita na parte anterior, usando inf_block
:static inf_stat_t inf_dyn_block(istream_t *is, uint8_t *dst,
size_t dst_cap, size_t *dst_pos)
{
inf_stat_t s;
huffman_decoder_t litlen_dec, dist_dec;
s = init_dyn_decoders(is, &litlen_dec, &dist_dec);
if (s != HWINF_OK) {
return s;
}
return inf_block(is, dst, dst_cap, dst_pos, &litlen_dec, &dist_dec);
}
Os códigos litlen e dist para blocos dinâmicos de deflação são armazenados como uma série de comprimentos de palavras de código. Os comprimentos em si são codificados usando o terceiro código Huffman - codelen . Esse código é determinado pelo comprimento das palavras de código ( codelen_lens
) armazenadas no bloco (mencionei que é difícil?).No início do bloco dinâmico, existem 14 bits que determinam o número de comprimentos de litlen-, dist e codelen de palavras de código que precisam ser lidas no bloco:#define MIN_CODELEN_LENS 4
#define MAX_CODELEN_LENS 19
#define MIN_LITLEN_LENS 257
#define MAX_LITLEN_LENS 288
#define MIN_DIST_LENS 1
#define MAX_DIST_LENS 32
#define CODELEN_MAX_LIT 15
#define CODELEN_COPY 16
#define CODELEN_COPY_MIN 3
#define CODELEN_COPY_MAX 6
#define CODELEN_ZEROS 17
#define CODELEN_ZEROS_MIN 3
#define CODELEN_ZEROS_MAX 10
#define CODELEN_ZEROS2 18
#define CODELEN_ZEROS2_MIN 11
#define CODELEN_ZEROS2_MAX 138
static const int codelen_lengths_order[MAX_CODELEN_LENS] =
{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
static inf_stat_t init_dyn_decoders(istream_t *is,
huffman_decoder_t *litlen_dec,
huffman_decoder_t *dist_dec)
{
uint64_t bits;
size_t num_litlen_lens, num_dist_lens, num_codelen_lens;
uint8_t codelen_lengths[MAX_CODELEN_LENS];
uint8_t code_lengths[MAX_LITLEN_LENS + MAX_DIST_LENS];
size_t i, n, used;
int sym;
huffman_decoder_t codelen_dec;
bits = istream_bits(is);
num_litlen_lens = lsb(bits, 5) + MIN_LITLEN_LENS;
bits >>= 5;
assert(num_litlen_lens <= MAX_LITLEN_LENS);
num_dist_lens = lsb(bits, 5) + MIN_DIST_LENS;
bits >>= 5;
assert(num_dist_lens <= MAX_DIST_LENS);
num_codelen_lens = lsb(bits, 4) + MIN_CODELEN_LENS;
bits >>= 4;
assert(num_codelen_lens <= MAX_CODELEN_LENS);
if (!istream_advance(is, 5 + 5 + 4)) {
return HWINF_ERR;
}
Em seguida, vêm os comprimentos das palavras de código para o código codelen. Esses comprimentos são os valores usuais de três bits, mas gravados na ordem especial especificada em codelen_lengths_order
. Como é necessário determinar 19 comprimentos, apenas serão lidos a partir do fluxo num_codelen_lens
; tudo o resto é implicitamente nulo. Os comprimentos são listados em uma determinada ordem, para que os comprimentos zero caiam mais no final da lista e não sejam armazenados no bloco.
for (i = 0; i < num_codelen_lens; i++) {
bits = istream_bits(is);
codelen_lengths[codelen_lengths_order[i]] =
(uint8_t)lsb(bits, 3);
if (!istream_advance(is, 3)) {
return HWINF_ERR;
}
}
for (; i < MAX_CODELEN_LENS; i++) {
codelen_lengths[codelen_lengths_order[i]] = 0;
}
if (!huffman_decoder_init(&codelen_dec, codelen_lengths,
MAX_CODELEN_LENS)) {
return HWINF_ERR;
}
Ao definir o decodificador codelen, podemos ler os comprimentos das palavras de código litlen e dist do fluxo.
i = 0;
while (i < num_litlen_lens + num_dist_lens) {
bits = istream_bits(is);
sym = huffman_decode(&codelen_dec, (uint16_t)bits, &used);
bits >>= used;
if (!istream_advance(is, used)) {
return HWINF_ERR;
}
if (sym >= 0 && sym <= CODELEN_MAX_LIT) {
code_lengths[i++] = (uint8_t)sym;
}
16, 17 e 18 não são comprimentos reais, são indicadores de que o comprimento anterior precisa ser repetido várias vezes ou que você precisa repetir o comprimento zero: else if (sym == CODELEN_COPY) {
if (i < 1) {
return HWINF_ERR;
}
n = lsb(bits, 2) + CODELEN_COPY_MIN;
if (!istream_advance(is, 2)) {
return HWINF_ERR;
}
assert(n >= CODELEN_COPY_MIN && n <= CODELEN_COPY_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i] = code_lengths[i - 1];
i++;
}
} else if (sym == CODELEN_ZEROS) {
n = lsb(bits, 3) + CODELEN_ZEROS_MIN;
if (!istream_advance(is, 3)) {
return HWINF_ERR;
}
assert(n >= CODELEN_ZEROS_MIN &&
n <= CODELEN_ZEROS_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i++] = 0;
}
} else if (sym == CODELEN_ZEROS2) {
n = lsb(bits, 7) + CODELEN_ZEROS2_MIN;
if (!istream_advance(is, 7)) {
return HWINF_ERR;
}
assert(n >= CODELEN_ZEROS2_MIN &&
n <= CODELEN_ZEROS2_MAX);
if (i + n > num_litlen_lens + num_dist_lens) {
return HWINF_ERR;
}
while (n--) {
code_lengths[i++] = 0;
}
} else {
return HWINF_ERR;
}
}
Observe que os comprimentos litlen e dist são lidos um a um na matriz code_lengths
. Eles não podem ser lidos separadamente, porque as execuções de comprimento de código podem ser transferidas dos últimos comprimentos de litlen para os primeiros comprimentos dist.Depois de preparar os comprimentos das palavras de código, podemos configurar os decodificadores Huffman e retornar à tarefa de decodificar literais e backlinks: if (!huffman_decoder_init(litlen_dec, &code_lengths[0],
num_litlen_lens)) {
return HWINF_ERR;
}
if (!huffman_decoder_init(dist_dec, &code_lengths[num_litlen_lens],
num_dist_lens)) {
return HWINF_ERR;
}
return HWINF_OK;
}
Compressão (deflação)
Nas partes anteriores, criamos todas as ferramentas necessárias para a compressão Deflate: codificação Lempel-Ziv, Huffman, fluxos de bits e uma descrição dos três tipos de blocos Deflate. E nesta parte, reuniremos tudo para obter a compressão Deflate.Compressão O Lempel-Ziv analisa os dados de origem em uma sequência de backlinks e literais. Essa sequência deve ser dividida e codificada em blocos Deflate, conforme descrito na parte anterior. A escolha de um método de particionamento costuma ser chamada de bloqueio.. Por um lado, cada novo bloco significa algum tipo de sobrecarga, cujo volume depende do tipo de bloco e seu conteúdo. Menos blocos - menos sobrecarga. Por outro lado, esses custos de criação de um novo bloco podem compensar. Por exemplo, se as características dos dados permitirem executar com mais eficiência a codificação de Huffman e reduzir a quantidade total de dados gerados.O bloqueio é uma tarefa difícil de otimização. Alguns compressores (por exemplo, Zopfli ) tentam melhor que outros, mas a maioria simplesmente usa a abordagem gananciosa: eles emitem blocos assim que atingem um determinado tamanho.Diferentes tipos de blocos têm suas próprias restrições de tamanho:- Blocos não compactados não podem conter mais que 65.535 bytes.
- Os códigos fixos Huffman não têm um tamanho máximo.
- Os códigos dinâmicos de Huffman geralmente não têm um tamanho máximo, mas como nossa implementação do algoritmo Huffman usa sequências de 16 bits, estamos limitados a 65.535 caracteres.
Para usar blocos de qualquer tipo livremente, limite seu tamanho a 65.534 bytes:
#define MAX_BLOCK_LEN_BYTES 65534
Para rastrear o fluxo de bits de saída e o conteúdo do bloco atual durante a compactação, usaremos a estrutura:typedef struct deflate_state_t deflate_state_t;
struct deflate_state_t {
ostream_t os;
const uint8_t *block_src;
size_t block_len;
size_t block_len_bytes;
uint16_t litlen_freqs[LITLEN_MAX + 1];
uint16_t dist_freqs[DISTSYM_MAX + 1];
struct {
uint16_t distance;
union {
uint16_t lit;
uint16_t len;
} u;
} block[MAX_BLOCK_LEN_BYTES + 1];
};
static void reset_block(deflate_state_t *s)
{
s->block_len = 0;
s->block_len_bytes = 0;
memset(s->litlen_freqs, 0, sizeof(s->litlen_freqs));
memset(s->dist_freqs, 0, sizeof(s->dist_freqs));
}
Para adicionar resultados de trabalho ao bloco, lz77_compress
usaremos as funções de retorno de chamada e, ao atingir o tamanho máximo, gravaremos o bloco no fluxo de bits:static bool lit_callback(uint8_t lit, void *aux)
{
deflate_state_t *s = aux;
if (s->block_len_bytes + 1 > MAX_BLOCK_LEN_BYTES) {
if (!write_block(s, false)) {
return false;
}
s->block_src += s->block_len_bytes;
reset_block(s);
}
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
s->block[s->block_len ].distance = 0;
s->block[s->block_len++].u.lit = lit;
s->block_len_bytes++;
s->litlen_freqs[lit]++;
return true;
}
static bool backref_callback(size_t dist, size_t len, void *aux)
{
deflate_state_t *s = aux;
if (s->block_len_bytes + len > MAX_BLOCK_LEN_BYTES) {
if (!write_block(s, false)) {
return false;
}
s->block_src += s->block_len_bytes;
reset_block(s);
}
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
s->block[s->block_len ].distance = (uint16_t)dist;
s->block[s->block_len++].u.len = (uint16_t)len;
s->block_len_bytes += len;
assert(len >= MIN_LEN && len <= MAX_LEN);
assert(dist >= MIN_DISTANCE && dist <= MAX_DISTANCE);
s->litlen_freqs[len2litlen[len]]++;
s->dist_freqs[distance2dist[dist]]++;
return true;
}
O mais interessante é a gravação de blocos. Se o bloco não estiver compactado, tudo será simples:static bool write_uncomp_block(deflate_state_t *s, bool final)
{
uint8_t len_nlen[4];
if (!ostream_write(&s->os, (0x0 << 1) | final, 3)) {
return false;
}
len_nlen[0] = (uint8_t)(s->block_len_bytes >> 0);
len_nlen[1] = (uint8_t)(s->block_len_bytes >> 8);
len_nlen[2] = ~len_nlen[0];
len_nlen[3] = ~len_nlen[1];
if (!ostream_write_bytes_aligned(&s->os, len_nlen, sizeof(len_nlen))) {
return false;
}
if (!ostream_write_bytes_aligned(&s->os, s->block_src,
s->block_len_bytes)) {
return false;
}
return true;
}
Para escrever um bloco estático de Huffman, primeiro geramos códigos canônicos com base em comprimentos fixos de palavras de código para códigos litlen e dist. Em seguida, iteramos o bloco, anotando os caracteres que usam esses códigos:static bool write_static_block(deflate_state_t *s, bool final)
{
huffman_encoder_t litlen_enc, dist_enc;
if (!ostream_write(&s->os, (0x1 << 1) | final, 3)) {
return false;
}
huffman_encoder_init2(&litlen_enc, fixed_litlen_lengths,
sizeof(fixed_litlen_lengths) /
sizeof(fixed_litlen_lengths[0]));
huffman_encoder_init2(&dist_enc, fixed_dist_lengths,
sizeof(fixed_dist_lengths) /
sizeof(fixed_dist_lengths[0]));
return write_huffman_block(s, &litlen_enc, &dist_enc);
}
static bool write_huffman_block(deflate_state_t *s,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t i, nbits;
uint64_t distance, dist, len, litlen, bits, ebits;
for (i = 0; i < s->block_len; i++) {
if (s->block[i].distance == 0) {
litlen = s->block[i].u.lit;
assert(litlen <= LITLEN_EOB);
if (!ostream_write(&s->os,
litlen_enc->codewords[litlen],
litlen_enc->lengths[litlen])) {
return false;
}
continue;
}
len = s->block[i].u.len;
litlen = len2litlen[len];
bits = litlen_enc->codewords[litlen];
nbits = litlen_enc->lengths[litlen];
ebits = len - litlen_tbl[litlen - LITLEN_TBL_OFFSET].base_len;
bits |= ebits << nbits;
nbits += litlen_tbl[litlen - LITLEN_TBL_OFFSET].ebits;
distance = s->block[i].distance;
dist = distance2dist[distance];
bits |= (uint64_t)dist_enc->codewords[dist] << nbits;
nbits += dist_enc->lengths[dist];
ebits = distance - dist_tbl[dist].base_dist;
bits |= ebits << nbits;
nbits += dist_tbl[dist].ebits;
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
}
return true;
}
Obviamente, escrever blocos dinâmicos Huffman é mais difícil porque eles contêm codificação complicada de códigos litlen e dist. Para representar essa codificação, usamos a seguinte estrutura:typedef struct codelen_sym_t codelen_sym_t;
struct codelen_sym_t {
uint8_t sym;
uint8_t count;
};
Primeiro, descartamos a cauda de seus comprimentos zero das palavras de código litlen e dist e, em seguida, as copiamos em uma matriz regular para a codificação subsequente. Não podemos descartar todos os zeros: é impossível codificar um bloco Deflate se não houver um único código dist. Também é impossível ter menos de 257 códigos litlen, mas como sempre temos um marcador de final de bytes, sempre haverá um comprimento de código diferente de zero para um caractere de 256.
static size_t encode_dist_litlen_lens(const uint8_t *litlen_lens,
const uint8_t *dist_lens,
codelen_sym_t *encoded,
size_t *num_litlen_lens,
size_t *num_dist_lens)
{
size_t i, n;
uint8_t lens[LITLEN_MAX + 1 + DISTSYM_MAX + 1];
*num_litlen_lens = LITLEN_MAX + 1;
*num_dist_lens = DISTSYM_MAX + 1;
assert(litlen_lens[LITLEN_EOB] != 0 && "EOB len should be non-zero.");
while (litlen_lens[*num_litlen_lens - 1] == 0) {
(*num_litlen_lens)--;
}
assert(*num_litlen_lens >= MIN_LITLEN_LENS);
while (dist_lens[*num_dist_lens - 1] == 0 && *num_dist_lens > 1) {
(*num_dist_lens)--;
}
assert(*num_dist_lens >= MIN_DIST_LENS);
n = 0;
for (i = 0; i < *num_litlen_lens; i++) {
lens[n++] = litlen_lens[i];
}
for (i = 0; i < *num_dist_lens; i++) {
lens[n++] = dist_lens[i];
}
return encode_lens(lens, n, encoded);
}
Depois de adicionar os comprimentos de código em uma matriz, executamos a codificação usando caracteres especiais para executar os mesmos comprimentos de código.
static size_t encode_lens(const uint8_t *lens, size_t n, codelen_sym_t *encoded)
{
size_t i, j, num_encoded;
uint8_t count;
i = 0;
num_encoded = 0;
while (i < n) {
if (lens[i] == 0) {
for (j = i; j < min(n, i + CODELEN_ZEROS2_MAX) &&
lens[j] == 0; j++);
count = (uint8_t)(j - i);
if (count < CODELEN_ZEROS_MIN) {
encoded[num_encoded++].sym = 0;
i++;
continue;
}
if (count <= CODELEN_ZEROS_MAX) {
assert(count >= CODELEN_ZEROS_MIN &&
count <= CODELEN_ZEROS_MAX);
encoded[num_encoded].sym = CODELEN_ZEROS;
encoded[num_encoded++].count = count;
} else {
assert(count >= CODELEN_ZEROS2_MIN &&
count <= CODELEN_ZEROS2_MAX);
encoded[num_encoded].sym = CODELEN_ZEROS2;
encoded[num_encoded++].count = count;
}
i = j;
continue;
}
encoded[num_encoded++].sym = lens[i++];
for (j = i; j < min(n, i + CODELEN_COPY_MAX) &&
lens[j] == lens[i - 1]; j++);
count = (uint8_t)(j - i);
if (count >= CODELEN_COPY_MIN) {
assert(count >= CODELEN_COPY_MIN &&
count <= CODELEN_COPY_MAX);
encoded[num_encoded].sym = CODELEN_COPY;
encoded[num_encoded++].count = count;
i = j;
continue;
}
}
return num_encoded;
}
Os caracteres usados para codificação serão gravados usando o código Huffman - codelen. Os comprimentos das palavras de código do código codelen são gravados no bloco em uma ordem específica, para que comprimentos zero tenham mais probabilidade de terminar no final. Aqui está uma função que calcula quantos comprimentos devem ser escritos:static const int codelen_lengths_order[19] =
{ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
size_t count_codelen_lens(const uint8_t *codelen_lens)
{
size_t n = MAX_CODELEN_LENS;
while (codelen_lens[codelen_lengths_order[n - 1]] == 0) {
n--;
}
assert(n >= MIN_CODELEN_LENS && n <= MAX_CODELEN_LENS);
return n;
}
Suponha que já definimos os códigos litlen e dist, configuramos a codificação dos comprimentos de suas palavras de código e o código para esses comprimentos. Agora podemos escrever um bloco dinâmico de Huffman:static bool write_dynamic_block(deflate_state_t *s, bool final,
size_t num_litlen_lens, size_t num_dist_lens,
size_t num_codelen_lens,
const huffman_encoder_t *codelen_enc,
const codelen_sym_t *encoded_lens,
size_t num_encoded_lens,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t i;
uint8_t codelen, sym;
size_t nbits;
uint64_t bits, hlit, hdist, hclen, count;
bits = (0x2 << 1) | final;
nbits = 3;
hlit = num_litlen_lens - MIN_LITLEN_LENS;
bits |= hlit << nbits;
nbits += 5;
hdist = num_dist_lens - MIN_DIST_LENS;
bits |= hdist << nbits;
nbits += 5;
hclen = num_codelen_lens - MIN_CODELEN_LENS;
bits |= hclen << nbits;
nbits += 4;
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
for (i = 0; i < num_codelen_lens; i++) {
codelen = codelen_enc->lengths[codelen_lengths_order[i]];
if (!ostream_write(&s->os, codelen, 3)) {
return false;
}
}
for (i = 0; i < num_encoded_lens; i++) {
sym = encoded_lens[i].sym;
bits = codelen_enc->codewords[sym];
nbits = codelen_enc->lengths[sym];
count = encoded_lens[i].count;
if (sym == CODELEN_COPY) {
bits |= (count - CODELEN_COPY_MIN) << nbits;
nbits += 2;
} else if (sym == CODELEN_ZEROS) {
bits |= (count - CODELEN_ZEROS_MIN) << nbits;
nbits += 3;
} else if (sym == CODELEN_ZEROS2) {
bits |= (count - CODELEN_ZEROS2_MIN) << nbits;
nbits += 7;
}
if (!ostream_write(&s->os, bits, nbits)) {
return false;
}
}
return write_huffman_block(s, litlen_enc, dist_enc);
}
Para cada bloco, queremos usar o tipo que requer o menor número de bits. O comprimento de um bloco não compactado pode ser calculado rapidamente:
static size_t uncomp_block_len(const deflate_state_t *s)
{
size_t bit_pos, padding;
bit_pos = ostream_bit_pos(&s->os) + 3;
padding = round_up(bit_pos, 8) - bit_pos;
return 3 + padding + 2 * 16 + s->block_len_bytes * 8;
}
Para blocos codificados por Huffman, você pode calcular o comprimento do corpo usando as frequências litlen- e dist de caracteres e comprimentos de palavras de código:
static size_t huffman_block_body_len(const deflate_state_t *s,
const uint8_t *litlen_lens,
const uint8_t *dist_lens)
{
size_t i, freq, len;
len = 0;
for (i = 0; i <= LITLEN_MAX; i++) {
freq = s->litlen_freqs[i];
len += litlen_lens[i] * freq;
if (i >= LITLEN_TBL_OFFSET) {
len += litlen_tbl[i - LITLEN_TBL_OFFSET].ebits * freq;
}
}
for (i = 0; i <= DISTSYM_MAX; i++) {
freq = s->dist_freqs[i];
len += dist_lens[i] * freq;
len += dist_tbl[i].ebits * freq;
}
return len;
}
O comprimento total do bloco estático é de 3 bits do cabeçalho mais o comprimento do corpo. Calcular o tamanho do cabeçalho de um bloco dinâmico requer muito mais trabalho:
static size_t dyn_block_len(const deflate_state_t *s, size_t num_codelen_lens,
const uint16_t *codelen_freqs,
const huffman_encoder_t *codelen_enc,
const huffman_encoder_t *litlen_enc,
const huffman_encoder_t *dist_enc)
{
size_t len, i, freq;
len = 3;
len += 5 + 5 + 4;
len += 3 * num_codelen_lens;
for (i = 0; i < MAX_CODELEN_LENS; i++) {
freq = codelen_freqs[i];
len += codelen_enc->lengths[i] * freq;
if (i == CODELEN_COPY) {
len += 2 * freq;
} else if (i == CODELEN_ZEROS) {
len += 3 * freq;
} else if (i == CODELEN_ZEROS2) {
len += 7 * freq;
}
}
return len + huffman_block_body_len(s, litlen_enc->lengths,
dist_enc->lengths);
}
Agora vamos juntar tudo e criar a função principal para escrever blocos:
static bool write_block(deflate_state_t *s, bool final)
{
size_t old_bit_pos, uncomp_len, static_len, dynamic_len;
huffman_encoder_t dyn_litlen_enc, dyn_dist_enc, codelen_enc;
size_t num_encoded_lens, num_litlen_lens, num_dist_lens;
codelen_sym_t encoded_lens[LITLEN_MAX + 1 + DISTSYM_MAX + 1];
uint16_t codelen_freqs[MAX_CODELEN_LENS] = {0};
size_t num_codelen_lens;
size_t i;
old_bit_pos = ostream_bit_pos(&s->os);
assert(s->block_len < sizeof(s->block) / sizeof(s->block[0]));
assert(s->litlen_freqs[LITLEN_EOB] == 0);
s->block[s->block_len ].distance = 0;
s->block[s->block_len++].u.lit = LITLEN_EOB;
s->litlen_freqs[LITLEN_EOB] = 1;
uncomp_len = uncomp_block_len(s);
static_len = 3 + huffman_block_body_len(s, fixed_litlen_lengths,
fixed_dist_lengths);
huffman_encoder_init(&dyn_litlen_enc, s->litlen_freqs,
LITLEN_MAX + 1, 15);
huffman_encoder_init(&dyn_dist_enc, s->dist_freqs, DISTSYM_MAX + 1, 15);
num_encoded_lens = encode_dist_litlen_lens(dyn_litlen_enc.lengths,
dyn_dist_enc.lengths,
encoded_lens,
&num_litlen_lens,
&num_dist_lens);
for (i = 0; i < num_encoded_lens; i++) {
codelen_freqs[encoded_lens[i].sym]++;
}
huffman_encoder_init(&codelen_enc, codelen_freqs, MAX_CODELEN_LENS, 7);
num_codelen_lens = count_codelen_lens(codelen_enc.lengths);
dynamic_len = dyn_block_len(s, num_codelen_lens, codelen_freqs,
&codelen_enc, &dyn_litlen_enc,
&dyn_dist_enc);
if (uncomp_len <= dynamic_len && uncomp_len <= static_len) {
if (!write_uncomp_block(s, final)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == uncomp_len);
} else if (static_len <= dynamic_len) {
if (!write_static_block(s, final)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == static_len);
} else {
if (!write_dynamic_block(s, final, num_litlen_lens,
num_dist_lens, num_codelen_lens,
&codelen_enc, encoded_lens,
num_encoded_lens, &dyn_litlen_enc,
&dyn_dist_enc)) {
return false;
}
assert(ostream_bit_pos(&s->os) - old_bit_pos == dynamic_len);
}
return true;
}
Por fim, o iniciador de todo o processo de compactação deve definir o estado inicial, iniciar a compactação Lempel-Ziv e escrever o bloco resultante:
bool hwdeflate(const uint8_t *src, size_t src_len, uint8_t *dst,
size_t dst_cap, size_t *dst_used)
{
deflate_state_t s;
ostream_init(&s.os, dst, dst_cap);
reset_block(&s);
s.block_src = src;
if (!lz77_compress(src, src_len, &lit_callback,
&backref_callback, &s)) {
return false;
}
if (!write_block(&s, true)) {
return false;
}
assert(s.block_src + s.block_len_bytes == src + src_len);
*dst_used = ostream_bytes_written(&s.os);
return true;
}
Formato de arquivo zip
Acima, examinamos como a compactação Deflate usada nos arquivos Zip funciona. E o próprio formato de arquivo? Nesta parte, examinaremos em detalhes sua estrutura e implementação. O código está disponível em zip.h e zip.c .Visão geral
O formato do arquivo é descrito na Nota do aplicativo PKZip :- Cada arquivo ou item de archive em um arquivo zip possui um cabeçalho de arquivo local com metadados sobre o item.
- . , , , Zip-.
- , . , . Zip-.
Cada item do arquivo compactado é compactado e armazenado individualmente. Isso significa que, mesmo que haja correspondências entre arquivos no arquivo morto, eles não serão levados em consideração para melhorar a compactação.A localização do catálogo central no final permite concluir gradualmente o arquivo morto. À medida que os elementos do arquivo são compactados, eles são adicionados ao arquivo morto. O índice é registrado após todos os tamanhos compactados, o que permite descobrir as compensações de todos os arquivos. Adicionar arquivos a um arquivo existente é bastante fácil, ele é colocado após o último elemento e o diretório central é substituído.A capacidade de criar arquivos gradualmente foi especialmente importante para disseminar informações sobre vários disquetes ou volumes. Enquanto compactado, o PKZip sugeriu que os usuários inserissem novos disquetes e gravassem o diretório central nos últimos (últimos). Para descompactar um arquivo compactado com vários volumes, o PKZip primeiro solicitou a gravação do último disquete para ler o diretório central e, em seguida, o restante do disquete necessário para extrair os arquivos solicitados.Isso pode surpreendê-lo, mas não havia uma regra proibindo ter vários arquivos com o mesmo nome no arquivo morto. Isso pode gerar muita confusão ao descompactar: se houver vários arquivos com o mesmo nome, qual você deve descompactar? Por sua vez, isso pode levar a problemas de segurança. Devido ao erro "Master Key" no Android (CVE-2013-4787 , slides e vídeo do relatório no Black Hat), um invasor pode ignorar as verificações do sistema operacional de assinatura criptográfica ao instalar programas. Os programas Android são distribuídos em arquivos APK , que são arquivos Zip. Como se viu, se o APK continha vários arquivos com o mesmo nome, o código de verificação de assinatura selecionou o último arquivo com o mesmo nome e o instalador selecionou o primeiro arquivo, ou seja, a verificação não foi realizada. Em outras palavras, essa pequena diferença entre as duas bibliotecas Zip tornou possível ignorar todo o modelo de segurança do sistema operacional.Ao contrário da maioria dos formatos, os arquivos zip não devem começar com uma assinatura ou número mágico. Geralmente, não é indicado que o arquivo Zip seja iniciado de qualquer maneira específica, o que permite criar arquivos válidos como Zip e com um formato diferente - arquivos poliglotas . Por exemplo, os arquivos Zip com extração automática (por exemplo, pkz204g.exe ) são geralmente arquivos executáveis e arquivos Zip: a primeira parte é executável, seguida por um arquivo Zip (que é descompactado pela parte executável). O sistema operacional pode executá-lo como executável, mas o programa Zip o abrirá como um arquivo Zip. Esse recurso pode fazer com que você não exija uma assinatura no início do arquivo.Embora esses arquivos poliglotas sejam inteligentes, eles podem levar a problemas de segurança, pois podem enganar os programas que tentam determinar o conteúdo do arquivo e também permitir a entrega de códigos maliciosos em um local com arquivos de diferentes tipos. Por exemplo, explora arquivos GIFAR usados , que ao mesmo tempo são imagens GIF corretas e arquivos Java (JAR, um tipo de arquivo Zip). Para obter mais informações sobre esse problema, consulte o artigo Abusando de formatos de arquivo (começando na página 18).Como veremos abaixo, os arquivos Zip usam campos de 32 bits para compensações e tamanhos, a fim de limitar o tamanho do arquivo morto e seus elementos a quatro gigabytes. Na nota de aplicação 4.5O PKWare adicionou extensões de formato, permitindo o uso de compensações e tamanhos de 64 bits. Os arquivos que usam essas extensões estão no formato Zip64, mas não serão considerados.Estruturas de dados
Fim da entrada do diretório central
O final de uma entrada de diretório central (EOCDR) é normalmente usado como ponto de partida para a leitura de um arquivo zip. Ele contém a localização e o tamanho do diretório central, além de comentários opcionais sobre todo o arquivo morto.Nos arquivos zip que ocupavam vários disquetes - ou volumes - o EOCDR também continha informações sobre qual disco estamos usando atualmente, em qual disco o diretório central é iniciado etc. Hoje, essa funcionalidade raramente é usada e o código neste artigo não processa esses arquivos.O EOCDR é determinado pela assinatura 'P' 'K', seguida pelos bytes 5 e 6. É seguida pela estrutura abaixo, os números são armazenados de acordo com o princípio little-endian:
struct eocdr {
uint16_t disk_nbr;
uint16_t cd_start_disk;
uint16_t disk_cd_entries;
uint16_t cd_entries;
uint32_t cd_size;
uint32_t cd_offset;
uint16_t comment_len;
const uint8_t *comment;
};
O EOCDR deve estar localizado no final do arquivo. Mas, como pode haver um comentário arbitrário de 16 bits, pode ser necessário encontrar uma posição específica:
#define READ16(p) ((p) += 2, read16le((p) - 2))
#define READ32(p) ((p) += 4, read32le((p) - 4))
#define EOCDR_BASE_SZ 22
#define EOCDR_SIGNATURE 0x06054b50
static bool find_eocdr(struct eocdr *r, const uint8_t *src, size_t src_len)
{
size_t comment_len;
const uint8_t *p;
uint32_t signature;
for (comment_len = 0; comment_len <= UINT16_MAX; comment_len++) {
if (src_len < EOCDR_BASE_SZ + comment_len) {
break;
}
p = &src[src_len - EOCDR_BASE_SZ - comment_len];
signature = READ32(p);
if (signature == EOCDR_SIGNATURE) {
r->disk_nbr = READ16(p);
r->cd_start_disk = READ16(p);
r->disk_cd_entries = READ16(p);
r->cd_entries = READ16(p);
r->cd_size = READ32(p);
r->cd_offset = READ32(p);
r->comment_len = READ16(p);
r->comment = p;
assert(p == &src[src_len - comment_len] &&
"All fields read.");
if (r->comment_len == comment_len) {
return true;
}
}
}
return false;
}
Gravar EOCDR é fácil. Esta função grava e retorna o número de bytes gravados:
#define WRITE16(p, x) (write16le((p), (x)), (p) += 2)
#define WRITE32(p, x) (write32le((p), (x)), (p) += 4)
static size_t write_eocdr(uint8_t *dst, const struct eocdr *r)
{
uint8_t *p = dst;
WRITE32(p, EOCDR_SIGNATURE);
WRITE16(p, r->disk_nbr);
WRITE16(p, r->cd_start_disk);
WRITE16(p, r->disk_cd_entries);
WRITE16(p, r->cd_entries);
WRITE32(p, r->cd_size);
WRITE32(p, r->cd_offset);
WRITE16(p, r->comment_len);
assert(p - dst == EOCDR_BASE_SZ);
if (r->comment_len != 0) {
memcpy(p, r->comment, r->comment_len);
p += r->comment_len;
}
return (size_t)(p - dst);
}
Cabeçalho do arquivo central
O diretório central consiste em cabeçalhos de arquivos centrais escritos um após o outro, um para cada item do arquivo morto. Cada cabeçalho começa com a assinatura 'P', 'K', 1, 2 e, em seguida, existe uma estrutura:#define EXT_ATTR_DIR (1U << 4)
#define EXT_ATTR_ARC (1U << 5)
struct cfh {
uint16_t made_by_ver;
uint16_t extract_ver;
uint16_t gp_flag;
uint16_t method;
uint16_t mod_time;
uint16_t mod_date;
uint32_t crc32;
uint32_t comp_size;
uint32_t uncomp_size;
uint16_t name_len;
uint16_t extra_len;
uint16_t comment_len;
uint16_t disk_nbr_start;
uint16_t int_attrs;
uint32_t ext_attrs;
uint32_t lfh_offset;
const uint8_t *name;
const uint8_t *extra;
const uint8_t *comment;
};
made_by_ver
e extract_ver
codifique informações sobre o sistema operacional e a versão do programa usado para adicionar esse item, bem como qual versão é necessária para recuperá-lo. Os oito bits mais importantes codificam o sistema operacional (por exemplo, 0 significa DOS, 3 significa Unix, 10 significa Windows NTFS) e os oito bits inferiores codificam a versão do software. Defina o valor decimal como 20, o que significa compatibilidade com o PKZip 2.0.gp_flag
contém sinalizadores diferentes. Nós estamos interessados:- Bit 0, indicando o fato de criptografia do elemento (não consideraremos isso);
- E os bits 1 e 2, codificando o nível de compactação Deflate (0 - normal, 1 - máximo, 2 - rápido, 3 - muito rápido).
method
codifica um método de compactação. 0 - dados não compactados, 8 - Exclusão aplicada. Outros valores estão relacionados a algoritmos antigos ou novos, mas quase todos os Zip usam esses dois valores.mod_time
e mod_date
contém a data e hora em que o arquivo foi modificado, codificado no formato MS-DOS . Usando esse código, converteremos os carimbos time_t
de data / hora C comuns para e do formato MS-DOS:
static time_t dos2ctime(uint16_t dos_date, uint16_t dos_time)
{
struct tm tm = {0};
tm.tm_sec = (dos_time & 0x1f) * 2;
tm.tm_min = (dos_time >> 5) & 0x3f;
tm.tm_hour = (dos_time >> 11);
tm.tm_mday = (dos_date & 0x1f);
tm.tm_mon = ((dos_date >> 5) & 0xf) - 1;
tm.tm_year = (dos_date >> 9) + 80;
tm.tm_isdst = -1;
return mktime(&tm);
}
static void ctime2dos(time_t t, uint16_t *dos_date, uint16_t *dos_time)
{
struct tm *tm = localtime(&t);
*dos_time = 0;
*dos_time |= tm->tm_sec / 2;
*dos_time |= tm->tm_min << 5;
*dos_time |= tm->tm_hour << 11;
*dos_date = 0;
*dos_date |= tm->tm_mday;
*dos_date |= (tm->tm_mon + 1) << 5;
*dos_date |= (tm->tm_year - 80) << 9;
}
O campo crc32
contém o valor do código redundante cíclico de dados não compactados. É usado para verificar a integridade dos dados após a recuperação. Implementação aqui: crc32.c .comp_size
e uncomp_size
conter o tamanho compactado e descompactado dos dados do arquivo do item. Os três campos a seguir contêm o comprimento do nome, comentário e dados adicionais imediatamente após o título. disk_nbr_start
Projetado para arquivos usando vários disquetes.int_attrs
e ext_attrs
descreva os atributos internos e externos do arquivo. Os internos estão relacionados ao conteúdo do arquivo, por exemplo, o bit baixo indica se o arquivo contém apenas texto. Atributos externos indicam se o arquivo está oculto, somente leitura, etc. O conteúdo desses campos depende do SO, em particular, domade_by_ver
. No DOS, os 8 bits inferiores contêm o byte de atributo do arquivo, que pode ser obtido na chamada de sistema Int 21 / AX = 4300h . Por exemplo, o bit 4 significa que é um diretório e o bit 5 significa que o atributo "archive" está definido (verdadeiro para a maioria dos arquivos no DOS). Tanto quanto eu entendo, por uma questão de compatibilidade, esses bits são definidos de maneira semelhante em outros sistemas operacionais. No Unix, os 16 bits altos desse campo contêm bits do modo de arquivo retornados por stat (2) em st_mode
.lfh_offset
nos diz onde procurar o cabeçalho do arquivo local. name
- nome do arquivo (linha C) e comment
- comentário opcional para este elemento do arquivo (linha C). extra
pode conter dados adicionais opcionais, como informações sobre o proprietário do arquivo Unix, data e hora mais precisas da alteração ou campos Zip64.Esta função é usada para ler os cabeçalhos centrais dos arquivos:
#define CFH_BASE_SZ 46
#define CFH_SIGNATURE 0x02014b50
static bool read_cfh(struct cfh *cfh, const uint8_t *src, size_t src_len,
size_t offset)
{
const uint8_t *p;
uint32_t signature;
if (offset > src_len || src_len - offset < CFH_BASE_SZ) {
return false;
}
p = &src[offset];
signature = READ32(p);
if (signature != CFH_SIGNATURE) {
return false;
}
cfh->made_by_ver = READ16(p);
cfh->extract_ver = READ16(p);
cfh->gp_flag = READ16(p);
cfh->method = READ16(p);
cfh->mod_time = READ16(p);
cfh->mod_date = READ16(p);
cfh->crc32 = READ32(p);
cfh->comp_size = READ32(p);
cfh->uncomp_size = READ32(p);
cfh->name_len = READ16(p);
cfh->extra_len = READ16(p);
cfh->comment_len = READ16(p);
cfh->disk_nbr_start = READ16(p);
cfh->int_attrs = READ16(p);
cfh->ext_attrs = READ32(p);
cfh->lfh_offset = READ32(p);
cfh->name = p;
cfh->extra = cfh->name + cfh->name_len;
cfh->comment = cfh->extra + cfh->extra_len;
assert(p == &src[offset + CFH_BASE_SZ] && "All fields read.");
if (src_len - offset - CFH_BASE_SZ <
cfh->name_len + cfh->extra_len + cfh->comment_len) {
return false;
}
return true;
}
static size_t write_cfh(uint8_t *dst, const struct cfh *cfh)
{
uint8_t *p = dst;
WRITE32(p, CFH_SIGNATURE);
WRITE16(p, cfh->made_by_ver);
WRITE16(p, cfh->extract_ver);
WRITE16(p, cfh->gp_flag);
WRITE16(p, cfh->method);
WRITE16(p, cfh->mod_time);
WRITE16(p, cfh->mod_date);
WRITE32(p, cfh->crc32);
WRITE32(p, cfh->comp_size);
WRITE32(p, cfh->uncomp_size);
WRITE16(p, cfh->name_len);
WRITE16(p, cfh->extra_len);
WRITE16(p, cfh->comment_len);
WRITE16(p, cfh->disk_nbr_start);
WRITE16(p, cfh->int_attrs);
WRITE32(p, cfh->ext_attrs);
WRITE32(p, cfh->lfh_offset);
assert(p - dst == CFH_BASE_SZ);
if (cfh->name_len != 0) {
memcpy(p, cfh->name, cfh->name_len);
p += cfh->name_len;
}
if (cfh->extra_len != 0) {
memcpy(p, cfh->extra, cfh->extra_len);
p += cfh->extra_len;
}
if (cfh->comment_len != 0) {
memcpy(p, cfh->comment, cfh->comment_len);
p += cfh->comment_len;
}
return (size_t)(p - dst);
}
Cabeçalho do arquivo local
Os dados de cada elemento do arquivo morto são precedidos por um cabeçalho de arquivo local, que repete a maioria das informações do cabeçalho central.É provável que a duplicação de dados nos cabeçalhos central e local tenha sido introduzida para que o PKZip não mantenha todo o diretório central na memória ao descompactar. Em vez disso, à medida que cada arquivo é extraído, seu nome e outras informações podem ser lidas no cabeçalho local. Além disso, cabeçalhos locais são úteis para recuperar arquivos de arquivos Zip nos quais o diretório central está ausente ou danificado.No entanto, essa redundância também é a principal fonte de incerteza. Por exemplo, o que acontece se os nomes dos arquivos nos cabeçalhos central e local não coincidirem? Isso geralmente leva a erros e problemas de segurança.Nem todas as informações do cabeçalho central são duplicadas. Por exemplo, campos com atributos de arquivo. Além disso, se o terceiro bit menos significativo gp_flags
(CRC-32) for definido, os campos compactados e descompactados serão redefinidos para zero e essas informações podem ser encontradas no bloco Descritor de Dados após os dados do próprio arquivo (não será considerado). Isso permite que você grave um cabeçalho local antes que o tamanho do arquivo do elemento seja conhecido ou para qual tamanho ele será compactado.O cabeçalho local começa com a assinatura 'P', 'K', 3, 4 e, em seguida, existe uma estrutura:
struct lfh {
uint16_t extract_ver;
uint16_t gp_flag;
uint16_t method;
uint16_t mod_time;
uint16_t mod_date;
uint32_t crc32;
uint32_t comp_size;
uint32_t uncomp_size;
uint16_t name_len;
uint16_t extra_len;
const uint8_t *name;
const uint8_t *extra;
};
Essas funções lêem e escrevem cabeçalhos locais, como outras estruturas de dados:
#define LFH_BASE_SZ 30
#define LFH_SIGNATURE 0x04034b50
static bool read_lfh(struct lfh *lfh, const uint8_t *src, size_t src_len,
size_t offset)
{
const uint8_t *p;
uint32_t signature;
if (offset > src_len || src_len - offset < LFH_BASE_SZ) {
return false;
}
p = &src[offset];
signature = READ32(p);
if (signature != LFH_SIGNATURE) {
return false;
}
lfh->extract_ver = READ16(p);
lfh->gp_flag = READ16(p);
lfh->method = READ16(p);
lfh->mod_time = READ16(p);
lfh->mod_date = READ16(p);
lfh->crc32 = READ32(p);
lfh->comp_size = READ32(p);
lfh->uncomp_size = READ32(p);
lfh->name_len = READ16(p);
lfh->extra_len = READ16(p);
lfh->name = p;
lfh->extra = lfh->name + lfh->name_len;
assert(p == &src[offset + LFH_BASE_SZ] && "All fields read.");
if (src_len - offset - LFH_BASE_SZ < lfh->name_len + lfh->extra_len) {
return false;
}
return true;
}
static size_t write_lfh(uint8_t *dst, const struct lfh *lfh)
{
uint8_t *p = dst;
WRITE32(p, LFH_SIGNATURE);
WRITE16(p, lfh->extract_ver);
WRITE16(p, lfh->gp_flag);
WRITE16(p, lfh->method);
WRITE16(p, lfh->mod_time);
WRITE16(p, lfh->mod_date);
WRITE32(p, lfh->crc32);
WRITE32(p, lfh->comp_size);
WRITE32(p, lfh->uncomp_size);
WRITE16(p, lfh->name_len);
WRITE16(p, lfh->extra_len);
assert(p - dst == LFH_BASE_SZ);
if (lfh->name_len != 0) {
memcpy(p, lfh->name, lfh->name_len);
p += lfh->name_len;
}
if (lfh->extra_len != 0) {
memcpy(p, lfh->extra, lfh->extra_len);
p += lfh->extra_len;
}
return (size_t)(p - dst);
}
Implementação do Zip Read
Usando as funções acima, implementamos a leitura do arquivo Zip na memória e obtemos um iterador para acessar os elementos do arquivo:typedef size_t zipiter_t;
typedef struct zip_t zip_t;
struct zip_t {
uint16_t num_members;
const uint8_t *comment;
uint16_t comment_len;
zipiter_t members_begin;
zipiter_t members_end;
const uint8_t *src;
size_t src_len;
};
bool zip_read(zip_t *zip, const uint8_t *src, size_t src_len)
{
struct eocdr eocdr;
struct cfh cfh;
struct lfh lfh;
size_t i, offset;
const uint8_t *comp_data;
zip->src = src;
zip->src_len = src_len;
if (!find_eocdr(&eocdr, src, src_len)) {
return false;
}
if (eocdr.disk_nbr != 0 || eocdr.cd_start_disk != 0 ||
eocdr.disk_cd_entries != eocdr.cd_entries) {
return false;
}
zip->num_members = eocdr.cd_entries;
zip->comment = eocdr.comment;
zip->comment_len = eocdr.comment_len;
offset = eocdr.cd_offset;
zip->members_begin = offset;
for (i = 0; i < eocdr.cd_entries; i++) {
if (!read_cfh(&cfh, src, src_len, offset)) {
return false;
}
if (cfh.gp_flag & 1) {
return false;
}
if (cfh.method != ZIP_STORED && cfh.method != ZIP_DEFLATED) {
return false;
}
if (cfh.method == ZIP_STORED &&
cfh.uncomp_size != cfh.comp_size) {
return false;
}
if (cfh.disk_nbr_start != 0) {
return false;
}
if (memchr(cfh.name, '\0', cfh.name_len) != NULL) {
return false;
}
if (!read_lfh(&lfh, src, src_len, cfh.lfh_offset)) {
return false;
}
comp_data = lfh.extra + lfh.extra_len;
if (cfh.comp_size > src_len - (size_t)(comp_data - src)) {
return false;
}
offset += CFH_BASE_SZ + cfh.name_len + cfh.extra_len +
cfh.comment_len;
}
zip->members_end = offset;
return true;
}
Como mencionei acima, os iteradores de elemento são simplesmente deslocados para o cabeçalho central do arquivo, através do qual você pode acessar os dados do elemento:typedef enum { ZIP_STORED = 0, ZIP_DEFLATED = 8 } method_t;
typedef struct zipmemb_t zipmemb_t;
struct zipmemb_t {
const uint8_t *name;
uint16_t name_len;
time_t mtime;
uint32_t comp_size;
const uint8_t *comp_data;
method_t method;
uint32_t uncomp_size;
uint32_t crc32;
const uint8_t *comment;
uint16_t comment_len;
bool is_dir;
zipiter_t next;
};
zipmemb_t zip_member(const zip_t *zip, zipiter_t it)
{
struct cfh cfh;
struct lfh lfh;
bool ok;
zipmemb_t m;
assert(it >= zip->members_begin && it < zip->members_end);
ok = read_cfh(&cfh, zip->src, zip->src_len, it);
assert(ok);
ok = read_lfh(&lfh, zip->src, zip->src_len, cfh.lfh_offset);
assert(ok);
m.name = cfh.name;
m.name_len = cfh.name_len;
m.mtime = dos2ctime(cfh.mod_date, cfh.mod_time);
m.comp_size = cfh.comp_size;
m.comp_data = lfh.extra + lfh.extra_len;
m.method = cfh.method;
m.uncomp_size = cfh.uncomp_size;
m.crc32 = cfh.crc32;
m.comment = cfh.comment;
m.comment_len = cfh.comment_len;
m.is_dir = (cfh.ext_attrs & EXT_ATTR_DIR) != 0;
m.next = it + CFH_BASE_SZ +
cfh.name_len + cfh.extra_len + cfh.comment_len;
assert(m.next <= zip->members_end);
return m;
}
Implementação de Registro Zip
Para gravar um arquivo zip no buffer de memória, primeiro você precisa descobrir quanta memória alocar para ele. E como não sabemos quantos dados compactaremos antes de tentar escrever, calculamos o limite superior com base nos tamanhos dos elementos não compactados:
uint32_t zip_max_size(uint16_t num_memb, const char *const *filenames,
const uint32_t *file_sizes, const char *comment)
{
size_t comment_len, name_len;
uint64_t total;
uint16_t i;
comment_len = (comment == NULL ? 0 : strlen(comment));
if (comment_len > UINT16_MAX) {
return 0;
}
total = EOCDR_BASE_SZ + comment_len;
for (i = 0; i < num_memb; i++) {
assert(filenames[i] != NULL);
name_len = strlen(filenames[i]);
if (name_len > UINT16_MAX) {
return 0;
}
total += CFH_BASE_SZ + name_len;
total += LFH_BASE_SZ + name_len;
total += file_sizes[i];
}
if (total > UINT32_MAX) {
return 0;
}
return (uint32_t)total;
}
Esse código grava o arquivo zip usando a compactação deflate de cada elemento, reduzindo seu tamanho:
uint32_t zip_write(uint8_t *dst, uint16_t num_memb,
const char *const *filenames,
const uint8_t *const *file_data,
const uint32_t *file_sizes,
const time_t *mtimes,
const char *comment,
void (*callback)(const char *filename, uint32_t size,
uint32_t comp_size))
{
uint16_t i;
uint8_t *p;
struct eocdr eocdr;
struct cfh cfh;
struct lfh lfh;
bool ok;
uint16_t name_len;
uint8_t *data_dst;
size_t comp_sz;
uint32_t lfh_offset, cd_offset, eocdr_offset;
p = dst;
for (i = 0; i < num_memb; i++) {
assert(filenames[i] != NULL);
assert(strlen(filenames[i]) <= UINT16_MAX);
name_len = (uint16_t)strlen(filenames[i]);
data_dst = p + LFH_BASE_SZ + name_len;
if (hwdeflate(file_data[i], file_sizes[i], data_dst,
file_sizes[i], &comp_sz) &&
comp_sz < file_sizes[i]) {
lfh.method = ZIP_DEFLATED;
assert(comp_sz <= UINT32_MAX);
lfh.comp_size = (uint32_t)comp_sz;
} else {
memcpy(data_dst, file_data[i], file_sizes[i]);
lfh.method = ZIP_STORED;
lfh.comp_size = file_sizes[i];
}
if (callback != NULL) {
callback(filenames[i], file_sizes[i], lfh.comp_size);
}
lfh.extract_ver = (0 << 8) | 20;
lfh.gp_flag = (lfh.method == ZIP_DEFLATED ? (0x1 << 1) : 0x0);
ctime2dos(mtimes[i], &lfh.mod_date, &lfh.mod_time);
lfh.crc32 = crc32(file_data[i], file_sizes[i]);
lfh.uncomp_size = file_sizes[i];
lfh.name_len = name_len;
lfh.extra_len = 0;
lfh.name = (const uint8_t*)filenames[i];
p += write_lfh(p, &lfh);
p += lfh.comp_size;
}
assert(p - dst <= UINT32_MAX);
cd_offset = (uint32_t)(p - dst);
lfh_offset = 0;
for (i = 0; i < num_memb; i++) {
ok = read_lfh(&lfh, dst, SIZE_MAX, lfh_offset);
assert(ok);
cfh.made_by_ver = lfh.extract_ver;
cfh.extract_ver = lfh.extract_ver;
cfh.gp_flag = lfh.gp_flag;
cfh.method = lfh.method;
cfh.mod_time = lfh.mod_time;
cfh.mod_date = lfh.mod_date;
cfh.crc32 = lfh.crc32;
cfh.comp_size = lfh.comp_size;
cfh.uncomp_size = lfh.uncomp_size;
cfh.name_len = lfh.name_len;
cfh.extra_len = 0;
cfh.comment_len = 0;
cfh.disk_nbr_start = 0;
cfh.int_attrs = 0;
cfh.ext_attrs = EXT_ATTR_ARC;
cfh.lfh_offset = lfh_offset;
cfh.name = lfh.name;
p += write_cfh(p, &cfh);
lfh_offset += LFH_BASE_SZ + lfh.name_len + lfh.comp_size;
}
assert(p - dst <= UINT32_MAX);
eocdr_offset = (uint32_t)(p - dst);
eocdr.disk_nbr = 0;
eocdr.cd_start_disk = 0;
eocdr.disk_cd_entries = num_memb;
eocdr.cd_entries = num_memb;
eocdr.cd_size = eocdr_offset - cd_offset;
eocdr.cd_offset = cd_offset;
eocdr.comment_len = (uint16_t)(comment == NULL ? 0 : strlen(comment));
eocdr.comment = (const uint8_t*)comment;
p += write_eocdr(p, &eocdr);
assert(p - dst <= zip_max_size(num_memb, filenames, file_sizes,
comment));
return (uint32_t)(p - dst);
}
Hwzip
Agora sabemos como ler e gravar arquivos Zip, como compactar e descomprimir os dados armazenados neles. Agora vamos escrever um programa Zip simples contendo todas essas ferramentas. O código está disponível em hwzip.c .Usaremos uma macro para tratamento simples de erros e várias funções auxiliares para alocação de memória verificada:#define PERROR_IF(cond, msg) if (cond) { perror(msg); exit(1); }
static void *xmalloc(size_t size)
{
void *ptr = malloc(size);
PERROR_IF(ptr == NULL, "malloc");
return ptr;
}
static void *xrealloc(void *ptr, size_t size)
{
ptr = realloc(ptr, size);
PERROR_IF(ptr == NULL, "realloc");
return ptr;
}
As outras duas funções são usadas para ler e gravar arquivos:static uint8_t *read_file(const char *filename, size_t *file_sz)
{
FILE *f;
uint8_t *buf;
size_t buf_cap;
f = fopen(filename, "rb");
PERROR_IF(f == NULL, "fopen");
buf_cap = 4096;
buf = xmalloc(buf_cap);
*file_sz = 0;
while (feof(f) == 0) {
if (buf_cap - *file_sz == 0) {
buf_cap *= 2;
buf = xrealloc(buf, buf_cap);
}
*file_sz += fread(&buf[*file_sz], 1, buf_cap - *file_sz, f);
PERROR_IF(ferror(f), "fread");
}
PERROR_IF(fclose(f) != 0, "fclose");
return buf;
}
static void write_file(const char *filename, const uint8_t *data, size_t n)
{
FILE *f;
f = fopen(filename, "wb");
PERROR_IF(f == NULL, "fopen");
PERROR_IF(fwrite(data, 1, n, f) != n, "fwrite");
PERROR_IF(fclose(f) != 0, "fclose");
}
Nosso programa Zip pode executar três funções: faça uma lista do conteúdo dos arquivos Zip e extraia-o, além de criar arquivos Zip. A listagem não é mais simples:static void list_zip(const char *filename)
{
uint8_t *zip_data;
size_t zip_sz;
zip_t z;
zipiter_t it;
zipmemb_t m;
printf("Listing ZIP archive: %s\n\n", filename);
zip_data = read_file(filename, &zip_sz);
if (!zip_read(&z, zip_data, zip_sz)) {
printf("Failed to parse ZIP file!\n");
exit(1);
}
if (z.comment_len != 0) {
printf("%.*s\n\n", (int)z.comment_len, z.comment);
}
for (it = z.members_begin; it != z.members_end; it = m.next) {
m = zip_member(&z, it);
printf("%.*s\n", (int)m.name_len, m.name);
}
printf("\n");
free(zip_data);
}
A extração é um pouco mais complicada. Usaremos funções auxiliares para finalização nula do nome do arquivo (para transmiti-lo fopen
) e descompactar:static char *terminate_str(const char *str, size_t n)
{
char *p = xmalloc(n + 1);
memcpy(p, str, n);
p[n] = '\0';
return p;
}
static uint8_t *inflate_member(const zipmemb_t *m)
{
uint8_t *p;
size_t src_used, dst_used;
assert(m->method == ZIP_DEFLATED);
p = xmalloc(m->uncomp_size);
if (hwinflate(m->comp_data, m->comp_size, &src_used, p, m->uncomp_size,
&dst_used) != HWINF_OK) {
free(p);
return NULL;
}
if (src_used != m->comp_size || dst_used != m->uncomp_size) {
free(p);
return NULL;
}
return p;
}
Nosso programa ignorará qualquer elemento de arquivo que tenha diretórios. Isso é feito para evitar os chamados ataques de desvio de caminho : um arquivo malicioso é usado para gravar o arquivo fora do diretório especificado pelo usuário. Leia os detalhes nas FAQ do Info-ZIP .static void extract_zip(const char *filename)
{
uint8_t *zip_data;
size_t zip_sz;
zip_t z;
zipiter_t it;
zipmemb_t m;
char *tname;
uint8_t *inflated;
const uint8_t *uncomp_data;
printf("Extracting ZIP archive: %s\n\n", filename);
zip_data = read_file(filename, &zip_sz);
if (!zip_read(&z, zip_data, zip_sz)) {
printf("Failed to read ZIP file!\n");
exit(1);
}
if (z.comment_len != 0) {
printf("%.*s\n\n", (int)z.comment_len, z.comment);
}
for (it = z.members_begin; it != z.members_end; it = m.next) {
m = zip_member(&z, it);
if (m.is_dir) {
printf(" (Skipping dir: %.*s)\n",
(int)m.name_len, m.name);
continue;
}
if (memchr(m.name, '/', m.name_len) != NULL ||
memchr(m.name, '\\', m.name_len) != NULL) {
printf(" (Skipping file in dir: %.*s)\n",
(int)m.name_len, m.name);
continue;
}
assert(m.method == ZIP_STORED || m.method == ZIP_DEFLATED);
printf(" %s: %.*s",
m.method == ZIP_STORED ? "Extracting" : " Inflating",
(int)m.name_len, m.name);
fflush(stdout);
if (m.method == ZIP_STORED) {
assert(m.uncomp_size == m.comp_size);
inflated = NULL;
uncomp_data = m.comp_data;
} else {
inflated = inflate_member(&m);
if (inflated == NULL) {
printf("Error: inflation failed!\n");
exit(1);
}
uncomp_data = inflated;
}
if (crc32(uncomp_data, m.uncomp_size) != m.crc32) {
printf("Error: CRC-32 mismatch!\n");
exit(1);
}
tname = terminate_str((const char*)m.name, m.name_len);
write_file(tname, uncomp_data, m.uncomp_size);
printf("\n");
free(inflated);
free(tname);
}
printf("\n");
free(zip_data);
}
Para criar um arquivo zip, leremos os arquivos de entrada e os alimentaremos zip_write
. Como a biblioteca C padrão não permite que você obtenha a hora da modificação do arquivo, usaremos a hora atual (deixo isso como uma lição de casa para corrigir esse recurso).void zip_callback(const char *filename, uint32_t size, uint32_t comp_size)
{
bool deflated = comp_size < size;
printf(" %s: %s", deflated ? "Deflated" : " Stored", filename);
if (deflated) {
printf(" (%u%%)", 100 - 100 * comp_size / size);
}
printf("\n");
}
static void create_zip(const char *zip_filename, const char *comment,
uint16_t n, const char *const *filenames)
{
time_t mtime;
time_t *mtimes;
uint8_t **file_data;
uint32_t *file_sizes;
size_t file_size, zip_size;
uint8_t *zip_data;
uint16_t i;
printf("Creating ZIP archive: %s\n\n", zip_filename);
if (comment != NULL) {
printf("%s\n\n", comment);
}
mtime = time(NULL);
file_data = xmalloc(sizeof(*file_data) * n);
file_sizes = xmalloc(sizeof(*file_sizes) * n);
mtimes = xmalloc(sizeof(*mtimes) * n);
for (i = 0; i < n; i++) {
file_data[i] = read_file(filenames[i], &file_size);
if (file_size >= UINT32_MAX) {
printf("%s is too large!\n", filenames[i]);
exit(1);
}
file_sizes[i] = (uint32_t)file_size;
mtimes[i] = mtime;
}
zip_size = zip_max_size(n, filenames, file_sizes, comment);
if (zip_size == 0) {
printf("zip writing not possible");
exit(1);
}
zip_data = xmalloc(zip_size);
zip_size = zip_write(zip_data, n, filenames,
(const uint8_t *const *)file_data,
file_sizes, mtimes, comment, zip_callback);
write_file(zip_filename, zip_data, zip_size);
printf("\n");
free(zip_data);
for (i = 0; i < n; i++) {
free(file_data[i]);
}
free(mtimes);
free(file_sizes);
free(file_data);
}
Por fim, main
verifica os argumentos da linha de comando e decide o que fazer:static void print_usage(const char *argv0)
{
printf("Usage:\n\n");
printf(" %s list <zipfile>\n", argv0);
printf(" %s extract <zipfile>\n", argv0);
printf(" %s create <zipfile> [-c <comment>] <files...>\n", argv0);
printf("\n");
}
int main(int argc, char **argv) {
printf("\n");
printf("HWZIP " VERSION " -- A very simple ZIP program ");
printf("from https://www.hanshq.net/zip.html\n");
printf("\n");
if (argc == 3 && strcmp(argv[1], "list") == 0) {
list_zip(argv[2]);
} else if (argc == 3 && strcmp(argv[1], "extract") == 0) {
extract_zip(argv[2]);
} else if (argc >= 3 && strcmp(argv[1], "create") == 0) {
if (argc >= 5 && strcmp(argv[3], "-c") == 0) {
create_zip(argv[2], argv[4], (uint16_t)(argc - 5),
(const char *const *)&argv[5]);
} else {
create_zip(argv[2], NULL, (uint16_t)(argc - 3),
(const char *const *)&argv[3]);
}
} else {
print_usage(argv[0]);
return 1;
}
return 0;
}
Instruções de montagem
Um conjunto completo de arquivos de origem está disponível em hwzip-1.0.zip . Como compilar o HWZip no Linux ou Mac:$ clang generate_tables.c && ./a.out > tables.c
$ clang -O3 -DNDEBUG -march=native -o hwzip crc32.c deflate.c huffman.c \
hwzip.c lz77.c tables.c zip.c
No Windows, no prompt de comando do desenvolvedor no Visual Studio (se você não possui o Visual Studio, faça o download das ferramentas de criação ):cl /TC generate_tables.c && generate_tables > tables.c
cl /O2 /DNDEBUG /MT /Fehwzip.exe /TC crc32.c deflate.c huffman.c hwzip.c
lz77.c tables.c zip.c /link setargv.obj
Setargv.obj para expandir argumentos de linha de comando de caracteres curinga .)Conclusão
É incrível como a tecnologia está se desenvolvendo rápida e lentamente. O formato Zip foi criado há 30 anos, com base na tecnologia dos anos cinquenta e setenta. E, embora muita coisa tenha mudado desde então, os arquivos Zip permaneceram os mesmos e hoje são mais comuns do que nunca. Eu acho que será útil entender bem como eles funcionam.Exercícios
- Faça o HWZip registrar o tempo que levou para cada arquivo mudar, em vez do horário atual em que o arquivo foi criado. Use stat (2) no Linux ou Mac e GetFileTime no Windows. Ou adicione um sinalizador de linha de comando que permita ao usuário definir um horário específico para alterações no arquivo.
- gzip-. — , Deflate ( ). RFC 1952.
- Zip- . HWZip ,
read_file
mmap(2) Linux Mac CreateFileMapping Windows. - HWZip , Zip64. appnote.txt.