-
Notifications
You must be signed in to change notification settings - Fork 12
/
brotli-02.html
6432 lines (5567 loc) · 382 KB
/
brotli-02.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head profile="http://dublincore.org/documents/2008/08/04/dc-html/">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="robots" content="index,follow" />
<meta name="creator" content="rfcmarkup version 1.111" />
<link rel="schema.DC" href="http://purl.org/dc/elements/1.1/" />
<meta name="DC.Identifier" content="urn:ietf:id:alakuijala-brotli" />
<meta name="DC.Description.Abstract" content="This specification defines a lossless compressed data format that
compresses data using a combination of the LZ77 algorithm and Huffman
coding, with efficiency comparable to the best currently available
general-purpose compression methods." />
<meta name="DC.Creator" content="Szabadka, Zoltan" />
<meta name="DC.Creator" content="Alakuijala, Jyrki" />
<meta name="DC.Date.Issued" content="2014-10-27" />
<meta name="DC.Title" content="Brotli Compressed Data Format" />
<link rel="icon" href="/images/id.png" type="image/png" />
<link rel="shortcut icon" href="/images/id.png" type="image/png" />
<title>draft-alakuijala-brotli-02 - Brotli Compressed Data Format</title>
<style type="text/css">
body {
margin: 0px 8px;
font-size: 1em;
}
h1, h2, h3, h4, h5, h6, .h1, .h2, .h3, .h4, .h5, .h6 {
font-weight: bold;
line-height: 0pt;
display: inline;
white-space: pre;
font-family: monospace;
font-size: 1em;
font-weight: bold;
}
pre {
font-size: 1em;
margin-top: 0px;
margin-bottom: 0px;
}
.pre {
white-space: pre;
font-family: monospace;
}
.header{
font-weight: bold;
}
.newpage {
page-break-before: always;
}
.invisible {
text-decoration: none;
color: white;
}
a.selflink {
color: black;
text-decoration: none;
}
@media print {
body {
font-family: monospace;
font-size: 10.5pt;
}
h1, h2, h3, h4, h5, h6 {
font-size: 1em;
}
a:link, a:visited {
color: inherit;
text-decoration: none;
}
.noprint {
display: none;
}
}
@media screen {
.grey, .grey a:link, .grey a:visited {
color: #777;
}
.docinfo {
background-color: #EEE;
}
.top {
border-top: 7px solid #EEE;
}
.bgwhite { background-color: white; }
.bgred { background-color: #F44; }
.bggrey { background-color: #666; }
.bgbrown { background-color: #840; }
.bgorange { background-color: #FA0; }
.bgyellow { background-color: #EE0; }
.bgmagenta{ background-color: #F4F; }
.bgblue { background-color: #66F; }
.bgcyan { background-color: #4DD; }
.bggreen { background-color: #4F4; }
.legend { font-size: 90%; }
.cplate { font-size: 70%; border: solid grey 1px; }
}
</style>
<!--[if IE]>
<style>
body {
font-size: 13px;
margin: 10px 10px;
}
</style>
<![endif]-->
<script type="text/javascript"><!--
function addHeaderTags() {
var spans = document.getElementsByTagName("span");
for (var i=0; i < spans.length; i++) {
var elem = spans[i];
if (elem) {
var level = elem.getAttribute("class");
if (level == "h1" || level == "h2" || level == "h3" || level == "h4" || level == "h5" || level == "h6") {
elem.innerHTML = "<"+level+">"+elem.innerHTML+"</"+level+">";
}
}
}
}
var legend_html = "Colour legend:<br /> <table> <tr><td>Unknown:</td> <td><span class='cplate bgwhite'> </span></td></tr> <tr><td>Draft:</td> <td><span class='cplate bgred'> </span></td></tr> <tr><td>Informational:</td> <td><span class='cplate bgorange'> </span></td></tr> <tr><td>Experimental:</td> <td><span class='cplate bgyellow'> </span></td></tr> <tr><td>Best Common Practice:</td> <td><span class='cplate bgmagenta'> </span></td></tr> <tr><td>Proposed Standard:</td> <td><span class='cplate bgblue'> </span></td></tr> <tr><td>Draft Standard (old designation):</td> <td><span class='cplate bgcyan'> </span></td></tr> <tr><td>Internet Standard:</td> <td><span class='cplate bggreen'> </span></td></tr> <tr><td>Historic:</td> <td><span class='cplate bggrey'> </span></td></tr> <tr><td>Obsolete:</td> <td><span class='cplate bgbrown'> </span></td></tr> </table>";
function showElem(id) {
var elem = document.getElementById(id);
elem.innerHTML = eval(id+"_html");
elem.style.visibility='visible';
}
function hideElem(id) {
var elem = document.getElementById(id);
elem.style.visibility='hidden';
elem.innerHTML = "";
}
// -->
</script>
</head>
<body onload="addHeaderTags()">
<div style="height: 13px;">
<div onmouseover="this.style.cursor='pointer';"
onclick="showElem('legend');"
onmouseout="hideElem('legend')"
style="height: 6px; position: absolute;"
class="pre noprint docinfo bgred"
title="Click for colour legend." > </div>
<div id="legend"
class="docinfo noprint pre legend"
style="position:absolute; top: 4px; left: 4ex; visibility:hidden; background-color: white; padding: 4px 9px 5px 7px; border: solid #345 1px; "
onmouseover="showElem('legend');"
onmouseout="hideElem('legend');">
</div>
</div>
<span class="pre noprint docinfo top">[<a href="../html/" title="Document search and retrieval page">Docs</a>] [<a href="https://tools.ietf.org/id/draft-alakuijala-brotli-02.txt" title="Plaintext version of this document">txt</a>|<a href="/pdf/draft-alakuijala-brotli-02.txt" title="PDF version of this document">pdf</a>] [<a href='https://datatracker.ietf.org/doc/draft-alakuijala-brotli' title='IESG Datatracker information for this document'>Tracker</a>] [<a href="mailto:[email protected]?subject=draft-alakuijala-brotli%20" title="Send email to the document authors">Email</a>] [<a href="/rfcdiff?difftype=--hwdiff&url2=draft-alakuijala-brotli-02.txt" title="Inline diff (wdiff)">Diff1</a>] [<a href="/rfcdiff?url2=draft-alakuijala-brotli-02.txt" title="Side-by-side diff">Diff2</a>] [<a href="/idnits?url=https://tools.ietf.org/id/draft-alakuijala-brotli-02.txt" title="Run an idnits check of this document">Nits</a>] [<a href="https://datatracker.ietf.org/ipr/search/?option=document_search&document_search=draft-alakuijala-brotli" title="IPR disclosures related to this document">IPR</a>] </span><br />
<span class="pre noprint docinfo"> </span><br />
<span class="pre noprint docinfo">Versions: <a href="./draft-alakuijala-brotli-01">01</a> <a href="./draft-alakuijala-brotli-02">02</a> </span><br />
<span class="pre noprint docinfo"> </span><br />
<pre>
Network Working Group J. Alakuijala
Internet-Draft Z. Szabadka
Intended Status: Informational Google, Inc
Expires: April 27, 2015 October 2014
<span class="h1">Brotli Compressed Data Format</span>
<span class="h1">draft-alakuijala-brotli-02</span>
Abstract
This specification defines a lossless compressed data format that
compresses data using a combination of the LZ77 algorithm and Huffman
coding, with efficiency comparable to the best currently available
general-purpose compression methods.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of <a href="./bcp78">BCP 78</a> and <a href="./bcp79">BCP 79</a>.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at <a href="http://datatracker.ietf.org/drafts/current/">http://datatracker.ietf.org/drafts/current/</a>.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on April 27, 2015.
Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to <a href="./bcp78">BCP 78</a> and the IETF Trust's Legal
Provisions Relating to IETF Documents
(<a href="http://trustee.ietf.org/license-info">http://trustee.ietf.org/license-info</a>) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must
include Simplified BSD License text as described in <a href="#section-4">Section 4</a>.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 1]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-2" id="page-2" href="#page-2" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
Table of Contents
<a href="#section-1">1</a>. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-1.1">1.1</a>. Purpose . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-1.2">1.2</a>. Intended audience . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-1.3">1.3</a>. Scope . . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-3">3</a>
<a href="#section-1.4">1.4</a>. Compliance . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-4">4</a>
<a href="#section-1.5">1.5</a>. Definitions of terms and conventions used . . . . . . . . <a href="#page-4">4</a>
<a href="#section-1.5.1">1.5.1</a>. Packing into bytes . . . . . . . . . . . . . . . . . <a href="#page-4">4</a>
<a href="#section-2">2</a>. Compressed representation overview . . . . . . . . . . . . . . <a href="#page-5">5</a>
<a href="#section-3">3</a>. Compressed representation of Huffman codes . . . . . . . . . . <a href="#page-7">7</a>
<a href="#section-3.1">3.1</a>. Introduction to prefix and Huffman coding . . . . . . . . <a href="#page-7">7</a>
<a href="#section-3.2">3.2</a>. Use of Huffman coding in the "brotli" format . . . . . . . <a href="#page-8">8</a>
<a href="#section-3.3">3.3</a>. Alphabet sizes . . . . . . . . . . . . . . . . . . . . . <a href="#page-10">10</a>
<a href="#section-3.4">3.4</a>. Simple Huffman codes . . . . . . . . . . . . . . . . . . <a href="#page-10">10</a>
<a href="#section-3.5">3.5</a>. Complex Huffman codes . . . . . . . . . . . . . . . . . . <a href="#page-11">11</a>
<a href="#section-4">4</a>. Encoding of distances . . . . . . . . . . . . . . . . . . . . <a href="#page-13">13</a>
<a href="#section-5">5</a>. Encoding of literal insertion lengths and copy lengths . . . . <a href="#page-14">14</a>
<a href="#section-6">6</a>. Encoding of block switch commands . . . . . . . . . . . . . . <a href="#page-17">17</a>
<a href="#section-7">7</a>. Context modeling . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-18">18</a>
<a href="#section-7.1">7.1</a>. Context modes and context ID lookup for literals . . . . <a href="#page-18">18</a>
<a href="#section-7.2">7.2</a>. Context ID for distances . . . . . . . . . . . . . . . . <a href="#page-20">20</a>
<a href="#section-7.3">7.3</a>. Encoding of the context map . . . . . . . . . . . . . . . <a href="#page-20">20</a>
<a href="#section-8">8</a>. Static dictionary . . . . . . . . . . . . . . . . . . . . . . <a href="#page-21">21</a>
<a href="#section-9">9</a>. Compressed data format . . . . . . . . . . . . . . . . . . . . <a href="#page-23">23</a>
<a href="#section-9.1">9.1</a>. Format of the stream header . . . . . . . . . . . . . . . <a href="#page-23">23</a>
<a href="#section-9.2">9.2</a>. Format of the meta-block header . . . . . . . . . . . . . <a href="#page-24">24</a>
<a href="#section-9.3">9.3</a>. Format of the meta-block data . . . . . . . . . . . . . . <a href="#page-26">26</a>
<a href="#section-10">10</a>. Decoding algorithm . . . . . . . . . . . . . . . . . . . . . <a href="#page-27">27</a>
<a href="#section-11">11</a>. Security Considerations . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#section-12">12</a>. IANA Considerations . . . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#section-13">13</a>. Informative References . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#section-14">14</a>. Source code . . . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#appendix-A">Appendix A</a>. Static dictionary data . . . . . . . . . . . . . . . <a href="#page-29">29</a>
<a href="#appendix-B">Appendix B</a>. List of word transformations . . . . . . . . . . . . <a href="#page-110">110</a>
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . <a href="#page-112">112</a>
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 2]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-3" id="page-3" href="#page-3" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
<span class="h2"><a class="selflink" name="section-1" href="#section-1">1</a>. Introduction</span>
<span class="h3"><a class="selflink" name="section-1.1" href="#section-1.1">1.1</a>. Purpose</span>
The purpose of this specification is to define a lossless compressed
data format that:
* Is independent of CPU type, operating system, file system,
and character set, and hence can be used for interchange;
* Can be produced or consumed, even for an arbitrarily long
sequentially presented input data stream, using only an a
priori bounded amount of intermediate storage, and hence
can be used in data communications or similar structures,
such as Unix filters;
* Compresses data with a compression ratio comparable to the
best currently available general-purpose compression methods,
and in particular considerably better than the gzip program;
* Decompresses much faster than current LZMA implementations.
The data format defined by this specification does not attempt to:
* Allow random access to compressed data;
* Compress specialized data (e.g., raster graphics) as well
as the best currently available specialized algorithms.
<span class="h3"><a class="selflink" name="section-1.2" href="#section-1.2">1.2</a>. Intended audience</span>
This specification is intended for use by software implementers to
compress data into and/or decompress data from "brotli" format.
The text of the specification assumes a basic background in
programming at the level of bits and other primitive data
representations. Familiarity with the technique of Huffman coding is
helpful but not required.
This specification uses heavily the notations and terminology
introduced in the DEFLATE format specification [<a href="./rfc1951">RFC 1951</a>]. For the
sake of completeness, we always include the whole text of the
relevant parts of <a href="./rfc1951">RFC 1951</a>, therefore familiarity with the DEFLATE
format is helpful but not required.
The compressed data format defined in this specification is an
integral part of the WOFF 2.0 web font file format [<a href="#ref-WOFF2" title=""WOFF File Format 2.0"">WOFF2</a>], therefore
this specification is also intended for implementers of WOFF 2.0
compressors and decompressors.
<span class="h3"><a class="selflink" name="section-1.3" href="#section-1.3">1.3</a>. Scope</span>
The specification specifies a method for representing a sequence of
bytes as a (usually shorter) sequence of bits, and a method for
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 3]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-4" id="page-4" href="#page-4" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
packing the latter bit sequence into bytes.
<span class="h3"><a class="selflink" name="section-1.4" href="#section-1.4">1.4</a>. Compliance</span>
Unless otherwise indicated below, a compliant decompressor must be
able to accept and decompress any data set that conforms to all the
specifications presented here. A compliant compressor must produce
data sets that conform to all the specifications presented here.
<span class="h3"><a class="selflink" name="section-1.5" href="#section-1.5">1.5</a>. Definitions of terms and conventions used</span>
Byte: 8 bits stored or transmitted as a unit (same as an octet). For
this specification, a byte is exactly 8 bits, even on machines which
store a character on a number of bits different from eight. See
below for the numbering of bits within a byte.
String: a sequence of arbitrary bytes.
Bytes stored within a computer do not have a "bit order", since they
are always treated as a unit. However, a byte considered as an
integer between 0 and 255 does have a most- and least- significant
bit, and since we write numbers with the most- significant digit on
the left, we also write bytes with the most- significant bit on the
left. In the diagrams below, we number the bits of a byte so that
bit 0 is the least-significant bit, i.e., the bits are numbered:
+--------+
|76543210|
+--------+
Within a computer, a number may occupy multiple bytes. All multi-
byte numbers in the format described here are stored with the least-
significant byte first (at the lower memory address). For example,
the decimal number 520 is stored as:
0 1
+--------+--------+
|00001000|00000010|
+--------+--------+
^ ^
| |
| + more significant byte = 2 x 256
+ less significant byte = 8
<span class="h4"><a class="selflink" name="section-1.5.1" href="#section-1.5.1">1.5.1</a>. Packing into bytes</span>
This document does not address the issue of the order in which bits
of a byte are transmitted on a bit-sequential medium, since the final
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 4]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-5" id="page-5" href="#page-5" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
data format described here is byte- rather than bit-oriented.
However, we describe the compressed block format below as a sequence
of data elements of various bit lengths, not a sequence of bytes. We
must therefore specify how to pack these data elements into bytes to
form the final compressed byte sequence:
* Data elements are packed into bytes in order of
increasing bit number within the byte, i.e., starting
with the least-significant bit of the byte.
* Data elements other than Huffman codes are packed
starting with the least-significant bit of the data
element.
* Huffman codes are packed starting with the most-
significant bit of the code.
In other words, if one were to print out the compressed data as a
sequence of bytes, starting with the first byte at the *right* margin
and proceeding to the *left*, with the most- significant bit of each
byte on the left as usual, one would be able to parse the result from
right to left, with fixed-width elements in the correct MSB-to-LSB
order and Huffman codes in bit-reversed order (i.e., with the first
bit of the code in the relative LSB position).
<span class="h2"><a class="selflink" name="section-2" href="#section-2">2</a>. Compressed representation overview</span>
A compressed data set consists of a header and a series of meta-
blocks corresponding to successive meta-blocks of input data. The
meta-block sizes are limited to bytes and the maximum meta-block size
is 268,435,456 bytes.
The header contains the size of a sliding window on the input data
that is sufficient to keep on the intermediate storage at any given
point during decoding the stream.
Each meta-block is compressed using a combination of the LZ77
algorithm (Lempel-Ziv 1977, [<a href="#ref-LZ77" title=""A Universal Algorithm for Sequential Data Compression"">LZ77</a>]) and Huffman coding. The Huffman
trees for each block are independent of those for previous or
subsequent blocks; the LZ77 algorithm may use a reference to a
duplicated string occurring in a previous meta-block, up to sliding
window size input bytes before.
Each meta-block consists of two parts: a meta-block header that
describes the representation of the compressed data part, and a
compressed data part. The compressed data consists of a series of
commands. Each command consists of two parts: a sequence of literal
bytes (of strings that have not been detected as duplicated within
the sliding window), and a pointer to a duplicated string,
represented as a pair <length, backward distance>.
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 5]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-6" id="page-6" href="#page-6" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
Each command in the compressed data is represented using three kinds
of Huffman codes: one kind of code tree for the literal sequence
lengths (also referred to as literal insertion lengths) and backward
copy lengths (that is, a single code word represents two lengths, one
of the literal sequence and one of the backward copy), a separate
kind of code tree for literals, and a third kind of code tree for
distances. The code trees for each meta-block appear in a compact
form just before the compressed data in the meta-block header.
The sequence of each type of value in the representation of a command
(insert-and-copy lengths, literals and distances) within a meta-
block is further divided into blocks. In the "brotli" format, blocks
are not contiguous chunks of compressed data, but rather the pieces
of compressed data belonging to a block are interleaved with pieces
of data belonging to other blocks. Each meta-block can be logically
decomposed into a series of insert-and-copy length blocks, a series
of literal blocks and a series of distance blocks. These are also
called the three block categories: a meta-block has a series of
blocks for each block category. Note that the physical structure of
the meta-block is a series of commands, while the three series of
blocks is the logical structure. Consider the following example:
(IaC0, L0, L1, L2, D0)(IaC1, D1)(IaC2, L3, L4, D2)(IaC3, L5, D3)
The meta-block here has 4 commands, and each three types of symbols
within these commands can be rearranged for example into the
following logical block structure:
[IaC0, IaC1][IaC2, IaC3] <-- block types 0 and 1
[L0, L1][L2, L3, L4][L5] <-- block types 0, 1, and 0
[D0][D1, D2, D3] <-- block types 0 and 1
The subsequent blocks within each block category must have different
block types, but blocks further away in the block sequence can have
the same types. The block types are numbered from 0 to the maximum
block type number of 255 and the first block of each block category
must have type 0. The block structure of a meta-block is represented
by the sequence of block-switch commands for each block category,
where a block-switch command is a pair <block type, block length>.
The block-switch commands are represented in the compressed data
before the start of each new block using a Huffman code tree for
block types and a separate Huffman code tree for block lengths for
each block category. In the above example the physical layout of the
meta-block is the following:
IaC0 L0 L1 LBlockSwitch(1, 3) L2 D0 IaC1 DBlockSwitch(1, 1) D1
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 6]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-7" id="page-7" href="#page-7" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
IaCBlockSwitch(1, 2) IaC2 L3 L4 D2 IaC3 LBlockSwitch(0, 1) D3
Note that the block switch commands for the first blocks are not part
of the meta-block compressed data part, they are encoded in the meta-
block header. The code trees for block types and lengths (total of
six Huffman code trees) appear in a compact form in the meta-block
header.
Each type of value (insert-and-copy lengths, literals and distances)
can be encoded with any Huffman tree from a collection of Huffman
trees of the same kind appearing in the meta-block header. The
particular Huffman tree used can depend on two factors: the block
type of the block the value appears in, and the context of the value.
In the case of the literals, the context is the previous two bytes in
the input data, and in the case of distances, the context is the copy
length from the same command. For insert-and-copy lengths, no context
is used and the Huffman tree depends only on the block type (in fact,
the index of the Huffman tree is the block type number). In the case
of literals and distances, the context is mapped to a context ID in
the rage [0, 63] for literals and [0, 3] for distances and the matrix
of the Huffman tree indices for each block type and context ID,
called the context map, is encoded in a compact form in the meta-
block header.
In addition to the parts listed above (Huffman code trees for insert-
and-copy lengths, literals, distances, block types and block lengths
and the context map), the meta-block header contains the number of
input bytes in the meta-block and two additional parameters used in
the representation of copy distances (number of "postfix bits" and
number of direct distance codes).
<span class="h2"><a class="selflink" name="section-3" href="#section-3">3</a>. Compressed representation of Huffman codes</span>
<span class="h3"><a class="selflink" name="section-3.1" href="#section-3.1">3.1</a>. Introduction to prefix and Huffman coding</span>
Prefix coding represents symbols from an a priori known alphabet by
bit sequences (codes), one code for each symbol, in a manner such
that different symbols may be represented by bit sequences of
different lengths, but a parser can always parse an encoded string
unambiguously symbol-by-symbol.
We define a prefix code in terms of a binary tree in which the two
edges descending from each non-leaf node are labeled 0 and 1 and in
which the leaf nodes correspond one-for-one with (are labeled with)
the symbols of the alphabet; then the code for a symbol is the
sequence of 0's and 1's on the edges leading from the root to the
leaf labeled with that symbol. For example:
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 7]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-8" id="page-8" href="#page-8" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
/\ Symbol Code
0 1 ------ ----
/ \ A 00
/\ B B 1
0 1 C 011
/ \ D 010
A /\
0 1
/ \
D C
A parser can decode the next symbol from an encoded input stream by
walking down the tree from the root, at each step choosing the edge
corresponding to the next input bit.
Given an alphabet with known symbol frequencies, the Huffman
algorithm allows the construction of an optimal prefix code (one
which represents strings with those symbol frequencies using the
fewest bits of any possible prefix codes for that alphabet). Such a
code is called a Huffman code. (See [<a href="#ref-HUFFMAN" title=""A Method for the Construction of Minimum Redundancy Codes"">HUFFMAN</a>] in Chapter 5,
references for additional information on Huffman codes.)
Note that in the "brotli" format, the Huffman codes for the various
alphabets must not exceed certain maximum code lengths. This
constraint complicates the algorithm for computing code lengths from
symbol frequencies. Again, see Chapter 5, references for details.
<span class="h3"><a class="selflink" name="section-3.2" href="#section-3.2">3.2</a>. Use of Huffman coding in the "brotli" format</span>
The Huffman codes used for each alphabet in the "brotli" format are
canonical Huffman codes, which have two additional rules:
* All codes of a given bit length have lexicographically
consecutive values, in the same order as the symbols they
represent;
* Shorter codes lexicographically precede longer codes.
We could recode the example above to follow this rule as follows,
assuming that the order of the alphabet is ABCD:
Symbol Code
------ ----
A 10
B 0
C 110
D 111
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 8]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-9" id="page-9" href="#page-9" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
I.e., 0 precedes 10 which precedes 11x, and 110 and 111 are
lexicographically consecutive.
Given this rule, we can define the canonical Huffman code for an
alphabet just by giving the bit lengths of the codes for each symbol
of the alphabet in order; this is sufficient to determine the actual
codes. In our example, the code is completely defined by the sequence
of bit lengths (2, 1, 3, 3). The following algorithm generates the
codes as integers, intended to be read from most- to least-
significant bit. The code lengths are initially in tree[I].Len; the
codes are produced in tree[I].Code.
1) Count the number of codes for each code length. Let
bl_count[N] be the number of codes of length N, N >= 1.
2) Find the numerical value of the smallest code for each
code length:
code = 0;
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
code = (code + bl_count[bits-1]) << 1;
next_code[bits] = code;
}
3) Assign numerical values to all codes, using consecutive
values for all codes of the same length with the base
values determined at step 2. Codes that are never used
(which have a bit length of zero) must not be assigned a
value.
for (n = 0; n <= max_code; n++) {
len = tree[n].Len;
if (len != 0) {
tree[n].Code = next_code[len];
next_code[len]++;
}
}
Example:
Consider the alphabet ABCDEFGH, with bit lengths (3, 3, 3, 3, 3, 2,
4, 4). After step 1, we have:
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 9]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-10" id="page-10" href="#page-10" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
N bl_count[N]
- -----------
2 1
3 5
4 2
Step 2 computes the following next_code values:
N next_code[N]
- ------------
1 0
2 0
3 2
4 14
Step 3 produces the following code values:
Symbol Length Code
------ ------ ----
A 3 010
B 3 011
C 3 100
D 3 101
E 3 110
F 2 00
G 4 1110
H 4 1111
<span class="h3"><a class="selflink" name="section-3.3" href="#section-3.3">3.3</a>. Alphabet sizes</span>
Huffman codes are used for different purposes in the "brotli" format,
and each purpose has a different alphabet size. For literal codes the
alphabet size is 256. For insert-and-copy length codes the alphabet
size is 704. For block length codes, the alphabet size is 26. For
distance codes, block type codes and the Huffman codes used in
compressing the context map, the alphabet size is dynamic and is
based on other parameters.
<span class="h3"><a class="selflink" name="section-3.4" href="#section-3.4">3.4</a>. Simple Huffman codes</span>
The first two bits of the compressed representation of each Huffman
code distinguishes between simple and complex Huffman codes. If this
value is 1, then a simple Huffman code follows. Otherwise the value
indicates the number of leading zeros.
A simple Huffman code can have only up to four symbols with non- zero
code length. The format of the simple Huffman code is as follows:
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 10]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-11" id="page-11" href="#page-11" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
2 bits: value of 1 indicates a simple Huffman code
2 bits: NSYM - 1, where NSYM = # of symbols with non-zero
code length
NSYM symbols, each encoded using ALPHABET_BITS bits
1 bit: tree-select, present only for NSYM = 4
The value of ALPHABET_BITS depends on the alphabet of the Huffman
code: it is the smallest number of bits that can represent all
symbols in the alphabet. E.g. for the alphabet of literal bytes,
ALPHABET_BITS is 8. The value of each of the NSYM symbols above is
the value of the ALPHABETS_BITS width machine integer representing
the symbol modulo the alphabet size of the Huffman code.
The (non-zero) code lengths of the symbols can be reconstructed as
follows:
* if NSYM = 1, the code length for the one symbol is one at
this stage, but only to distinguish it from the other zero
code length symbols, when encoding this symbol in the
compressed data stream using this Huffman code later, no
actual bits are emitted. Similarly, when decoding a symbol
using this Huffman code, no bits are read and the one symbol
is returned.
* if NSYM = 2, both symbols have code length 1.
* if NSYM = 3, the code lengths for the symbols are 1, 2, 2 in
the order they appear in the representation of the simple
Huffman code.
* if NSYM = 4, the code lengths (in order of symbols decoded)
depend on the tree-select bit: 2, 2, 2, 2, (tree-select bit 0)
or 1, 2, 3, 3 (tree-select bit 1).
<span class="h3"><a class="selflink" name="section-3.5" href="#section-3.5">3.5</a>. Complex Huffman codes</span>
A complex Huffman code is a canonical Huffman code, defined by the
sequence of code lengths, as discussed in Paragraph 3.2, above. For
even greater compactness, the code length sequences themselves are
compressed using a Huffman code. The alphabet for code lengths is as
follows:
0 - 15: Represent code lengths of 0 - 15
16: Copy the previous non-zero code length 3 - 6 times
The next 2 bits indicate repeat length
(0 = 3, ... , 3 = 6)
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 11]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-12" id="page-12" href="#page-12" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
If this is the first code length, or all previous
code lengths are zero, a code length of 8 is
repeated 3 - 6 times
A repeated code length code of 16 modifies the
repeat count of the previous one as follows:
repeat count = (4 * (repeat count - 2)) +
(3 - 6 on the next 2 bits)
Example: Codes 7, 16 (+2 bits 11), 16 (+2 bits 10)
will expand to 22 code lengths of 7
(1 + 4 * (6 - 2) + 5)
17: Repeat a code length of 0 for 3 - 10 times.
(3 bits of length)
A repeated code length code of 17 modifies the
repeat count of the previous one as follows:
repeat count = (8 * (repeat count - 2)) +
(3 - 10 on the next 3 bits)
A code length of 0 indicates that the corresponding symbol in the
alphabet will not occur in the compressed data, and should not
participate in the Huffman code construction algorithm given earlier.
A complex Huffman code must have at least two non-zero code lengths.
The bit lengths of the Huffman code over the code length alphabet are
compressed with the following static Huffman code:
Symbol Code
------ ----
0 00
1 1110
2 110
3 01
4 10
5 1111
We can now define the format of the complex Huffman code as follows:
2 bits: HSKIP, values of 0, 2 or 3 represent the respective
number of leading zeros. (Value of 1 indicates the
Simple Huffman code.)
Code lengths for symbols in the code length alphabet given
just above, in the order: 1, 2, 3, 4, 0, 5, 17, 6, 16, 7,
8, 9, 10, 11, 12, 13, 14, 15
The code lengths of code length symbols are between 0 and
5 and they are represented with 2 - 5 bits according to
the static Huffman code above. A code length of 0 means
the corresponding code length symbol is not used.
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 12]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-13" id="page-13" href="#page-13" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
If HSKIP is 2 or 3, a respective number of leading code
lengths are implicit zeros and are not present in the
code lengths sequence above. If there are at least two
non-zero code lengths, any trailing zero code lengths are
omitted, i.e. the last code length in the sequence must
be non-zero. In this case the sum of (32 >> code length)
over all the non-zero code lengths must equal to 32.
Sequence of code lengths symbols, encoded using the code
length Huffman code. Any trailing 0 or 17 must be
omitted, i.e. the last encoded code length symbol must be
between 1 and 16. The sum of (32768 >> code length) over
all the non-zero code lengths in the alphabet, including
those encoded using repeat code(s) of 16, must equal to
32768.
<span class="h2"><a class="selflink" name="section-4" href="#section-4">4</a>. Encoding of distances</span>
As described in <a href="#section-2">Section 2</a>, one component of a compressed meta-block
is a sequence of backward distances. In this section we provide the
details to the encoding of distances.
Each distance in the compressed data part of a meta-block is
represented with a pair <distance code, extra bits>. The distance
code and the extra bits are encoded back-to-back, the distance code
is encoded using a Huffman code over the distance code alphabet,
while the extra bits value is encoded as a fixed-width machine
integer. The number of extra bits can be 0 - 24, and it is dependent
on the distance code.
To convert a distance code and associated extra bits to a backward
distance, we need the sequence of past distances and two additional
parameters, the number of "postfix bits", denoted by NPOSTFIX, and
the number of direct distance codes, denoted by NDIRECT. Both of
these parameters are encoded in the meta-block header. We will also
use the following derived parameter:
POSTFIX_MASK = ((1 << NPOSTFIX) - 1)
The first 16 distance codes are special short codes that reference
past distances as follows:
0: last distance
1: second last distance
2: third last distance
3: fourth last distance
4: last distance - 1
5: last distance + 1
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 13]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-14" id="page-14" href="#page-14" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
6: last distance - 2
7: last distance + 2
8: last distance - 3
9: last distance + 3
10: second last distance - 1
11: second last distance + 1
12: second last distance - 2
13: second last distance + 2
14: second last distance - 3
15: second last distance + 3
The ring-buffer of four last distances is initialized by the values
16, 15, 11 and 4 (i.e. the fourth last is set to 16, the third last
to 15, the second last to 11 and the last distance to 4) at the
beginning of the *stream* (as opposed to the beginning of the meta-
block) and it is not reset at meta-block boundaries. When a distance
code 0 appears, the distance it represents (i.e. the last distance in
the sequence of distances) is not pushed to the ring-buffer of last
distances, in other words, the expression "(second, third, fourth)
last distance" means the (second, third, fourth) last distance that
was not represented by a 0 distance code. Similarly, distances that
represent static dictionary words (see <a href="#section-8">Section 8</a>.) are not pushed to
the ringbuffer of last distances.
The next NDIRECT distance codes, from 16 to 15 + NDIRECT, represent
distances from 1 to NDIRECT. Neither the distance short codes, nor
the NDIRECT direct distance codes have any extra bits.
Distance codes 16 + NDIRECT and greater all have extra bits, the
number of extra bits for a distance code "dcode" is given by the
following formula:
ndistbits = 1 + ((dcode - NDIRECT - 16) >> (NPOSTFIX + 1))
The maximum number of extra bits is 24, therefore the size of the
distance code alphabet is (16 + NDIRECT + (48 << NPOSTFIX)).
Given a distance code "dcode" (>= 16 + NDIRECT), and extra bits
"dextra", the backward distance is given by the following formula:
hcode = (dcode - NDIRECT - 16) >> NPOSTFIX
lcode = (dcode - NDIRECT - 16) & POSTFIX_MASK
offset = ((2 + (hcode & 1)) << ndistbits) - 4;
distance = ((offset + dextra) << NPOSTFIX) + lcode + NDIRECT + 1
<span class="h2"><a class="selflink" name="section-5" href="#section-5">5</a>. Encoding of literal insertion lengths and copy lengths</span>
As described in <a href="#section-2">Section 2</a>, the literal insertion lengths and backward
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 14]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-15" id="page-15" href="#page-15" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
copy lengths are encoded using a single Huffman code. This section
provides the details to this encoding.
Each <insertion length, copy length> pair in the compressed data part
of a meta-block is represented with the following triplet:
<insert-and-copy length code, insert extra bits, copy extra bits>
The insert-and-copy length code, the insert extra bits and the copy
extra bits are encoded back-to-back, the insert-and-copy length code
is encoded using a Huffman code over the insert-and-copy length code
alphabet, while the extra bits values are encoded as fixed-width
machine integers. The number of insert and copy extra bits can be 0 -
24, and they are dependent on the insert-and-copy length code.
Some of the insert-and-copy length codes also express the fact that
the distance code of the distance in the same command is 0, i.e. the
distance component of the command is the same as that of the previous
command. In this case, the distance code and extra bits for the
distance are omitted from the compressed data stream.
We describe the insert-and-copy length code alphabet in terms of the
(not directly used) insert length code and copy length code
alphabets. The symbols of the insert length code alphabet, along with
the number of insert extra bits and the range of the insert lengths
are as follows:
Extra Extra Extra
Code Bits Lengths Code Bits Lengths Code Bits Lengths
---- ---- ------ ---- ---- ------- ---- ---- -------
0 0 0 8 2 10-13 16 6 130-193
1 0 1 9 2 14-17 17 7 194-321
2 0 2 10 3 18-25 18 8 322-577
3 0 3 11 3 26-33 19 9 578-1089
4 0 4 12 4 34-49 20 10 1090-2113
5 0 5 13 4 50-65 21 12 2114-6209
6 1 6,7 14 5 66-97 22 14 6210-22593
7 1 8,9 15 5 98-129 23 24 22594-16799809
The symbols of the copy length code alphabet, along with the number
of copy extra bits and the range of copy lengths are as follows:
<span class="grey">Alakuijala & Szabadka Expires April 27, 2015 [Page 15]</span>
</pre><!--NewPage--><pre class='newpage'><a name="page-16" id="page-16" href="#page-16" class="invisible"> </a>
<span class="grey">Internet-Draft Brotli October 2014</span>
Extra Extra Extra
Code Bits Lengths Code Bits Lengths Code Bits Lengths