Compactação

Este documento se aplica ao seguinte método: API Update (v4): threatListUpdates.fetch.

Sobre a compactação

A compactação é um recurso fundamental das APIs Safe Browsing (v4). A compactação reduz significativamente os requisitos de largura de banda, o que é particularmente relevante, mas não exclusivamente, para dispositivos móveis. No momento, o servidor da Navegação segura é compatível com a compactação Rice. Outros métodos de compactação podem ser adicionados no futuro.

A compactação é definida usando o campo supportedCompressions e CompressionType. Os clientes devem usar os tipos de compactação RICE e RAW. A Navegação segura usa o tipo COMPRESSION_TYPE_UNSPECIFIED quando o tipo de compactação não está definido (a compactação RAW será substituída).

O servidor do Navegação Segura também usará a compactação HTTP padrão para compactar ainda mais as respostas, independente do tipo de compactação selecionado, desde que o cliente defina o cabeçalho de compactação HTTP correto. Consulte o artigo da Wikipédia Compactação HTTP.

Compactação Rice

Conforme observado, o servidor da Navegação segura é compatível atualmente com a compactação Rice. Consulte o artigo da Wikipédia Codificação Golomb para uma discussão completa sobre a codificação Golomb-Rice.

Compactação/descompactação

O objeto RiceDeltaEncoding representa os dados com codificação Rice-Golomb e é usado para enviar índices de remoção compactados ou prefixos de hash compactados de 4 bytes. Prefixos de hash com mais de 4 bytes não serão compactados e serão exibidos no formato bruto.

Para índices de remoção, a lista de índices é classificada em ordem crescente e codificada em delta usando a codificação RICE. Para adições, os prefixos de hash de 4 bytes são interpretados novamente como uint32s pequenos, classificados em ordem crescente e codificados em delta usando a codificação RICE. Observe a diferença no formato de hash entre a compactação RICE e o RAW: os hashes brutos são bytes lexicograficamente classificados, enquanto os hashes RICE são uint32s classificados em ordem crescente (após a descompactação).

Ou seja, a lista de números inteiros [1, 5, 7, 13] será codificada como 1 (o primeiro valor) e os deltas [4, 2, 6].

O primeiro valor é armazenado no campo firstValue, e os deltas são codificados usando um codificador Golomb-Rice. O parâmetro k (veja abaixo) é armazenado em "riceParameter". O campo numEntries contém o número de deltas codificados no codificador Rice (três no exemplo acima, não quatro). O campo encodedData contém os deltas codificados reais.

Codificador/decodificador

No codificador/decodificador Rice, cada delta n é codificado como q e r, em que n = (q<<k) + r (ou n = q * (2**k) + r). k é uma constante e um parâmetro do codificador/decodificador Rice. Os valores de q e r são codificados no fluxo de bits usando esquemas de codificação diferentes.

O quociente q é codificado em codificação unária seguida por um 0. Ou seja, 3 seria codificado como 1110, 4 como 11110 e 7 como 11111110. O quociente q é decodificado primeiro.

O restante r é codificado usando a codificação binária truncada. Somente os k bits menos significativos de r são gravados (e, portanto, lidos) do fluxo de bits. O restante r é decodificado depois de q.

Codificador/decodificador de bits

O codificador Rice depende de um codificador/decodificador de bits em que bits únicos podem ser anexados ao codificador de bits. Ou seja, para codificar um quociente q que pode ter apenas dois bits.

O codificador de bits é uma lista de bytes (8 bits). Os bits são definidos do bit significativo mais baixo no primeiro byte para o bit mais significativo no primeiro byte. Se um byte tiver todos os bits já definidos, um novo byte (inicializado como zero) será anexado ao final da lista de bytes. Se o último byte não for totalmente usado, os bits significativos mais altos serão definidos como zero. Exemplo:

Bits adicionados	BitEncoder após adicionar bits
	[]
0	[00000000]
1	[00000010]
1	[00000110]
1,0,1	[00101110]
0,0,0	[00101110, 00000000]
1,1,0	[00101110, 00000110]