Jiahonzheng's Blog

Golang GZIP 源码分析

字数统计: 2.1k阅读时长: 10 min
2019/11/12 Share

GZIP

GZIP 是 GNU Zip 的缩写,最早应用于 UNIX 系统的文件压缩,现常应用于改进 Web 应用程序性能,其压缩比率在 3 到 10 倍左右,可大大节省服务器的网络带宽,具体说明可参照 RFC 1952 文档。

Golang 在 compress/gzip 包中对 GZIP 进行了实现,下面我们对实现代码进行剖析。

压缩

Golang 官方在 gzip.go 文件中实现了 GZIP 压缩算法。

核心原理

GZIP 使用 DEFLATE 算法进行压缩,流程如下:对于要压缩的文件,首先使用 LZ77 算法的一个变种进行压缩,随后对得到的结果进行 Huffman 编码。

LZ77 原理:如果文件中有两块内容相同的话,那么只要知道前一块的位置和大小,我们就可以确定后一块的内容。所以我们可以用(两者之间的距离,相同内容的长度)这样一对信息,来替换后一块内容。由于(两者之间的距离,相同内容的长度)这一对信息的大小,小于被替换内容的大小,所以文件得到了压缩。

Huffman 原理:读取整个文件,并统计每个符号(我们把字节的 256 种值看作是 256 种符号)的出现次数,建立建立 Huffman 树,得到每个符号的新编码。因此,对于文件中出现次数较多的符号,它的编码位数比较少;对于出现次数较少的符号,它的编码位数比较多。最后,我们把文件中的每个字节替换成各自的新编码。

相关定义

在实现中,定义了 Writer 结构体,其具体定义如下。

1
2
3
4
5
6
7
8
9
10
11
12
type Writer struct {
Header // written at first call to Write, Flush, or Close
w io.Writer
level int
wroteHeader bool
compressor *flate.Writer
digest uint32 // CRC-32, IEEE polynomial (section 8)
size uint32 // Uncompressed size (section 2.3.1)
closed bool
buf [10]byte
err error
}

其中的 compressor 是压缩算法(DEFLATE)的实现,level 指压缩级别,具体的压缩级别如下。

1
2
3
4
5
6
7
const (
NoCompression = flate.NoCompression
BestSpeed = flate.BestSpeed
BestCompression = flate.BestCompression
DefaultCompression = flate.DefaultCompression
HuffmanOnly = flate.HuffmanOnly
)

创建实例

我们可以调用 NewWriterNewWriterLevel 创建压缩器实例,其中的 NewWriter 本质是默认压缩级别NewWriterLevel 方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
func NewWriter(w io.Writer) *Writer {
z, _ := NewWriterLevel(w, DefaultCompression)
return z
}

func NewWriterLevel(w io.Writer, level int) (*Writer, error) {
if level < HuffmanOnly || level > BestCompression {
return nil, fmt.Errorf("gzip: invalid compression level: %d", level)
}
z := new(Writer)
z.init(w, level)
return z, nil
}

NewWriterLevel 函数中,我们先对压缩级别进行合法性检查,随后调用 init 方法初始化实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (z *Writer) init(w io.Writer, level int) {
compressor := z.compressor
if compressor != nil {
compressor.Reset(w)
}
*z = Writer{
Header: Header{
OS: 255, // unknown
},
w: w,
level: level,
compressor: compressor,
}
}

可以看到,在 init 函数中,我们只是简单地设置了 Writer 结构体,并未对 compressor 进行实例化之类的操作(这可是压缩算法的核心组件)。

init 函数中,我们还调用了 Reset 函数,其具体实现如下。

1
2
3
func (z *Writer) Reset(w io.Writer) {
z.init(w, z.level)
}

在该函数中,我们并没有重新生成压缩器实例,而是选择了复用,该设计能够降低运行时的内存开销。

压缩流程

在创建完压缩器实例后,我们可调用 Write 方法,实现对数据的压缩,具体代码如下。

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
func (z *Writer) Write(p []byte) (int, error) {
if z.err != nil {
return 0, z.err
}
var n int
// Write the GZIP header lazily.
if !z.wroteHeader {
z.wroteHeader = true
z.buf = [10]byte{0: gzipID1, 1: gzipID2, 2: gzipDeflate}
if z.Extra != nil {
z.buf[3] |= 0x04
}
if z.Name != "" {
z.buf[3] |= 0x08
}
if z.Comment != "" {
z.buf[3] |= 0x10
}
if z.ModTime.After(time.Unix(0, 0)) {
// Section 2.3.1, the zero value for MTIME means that the
// modified time is not set.
le.PutUint32(z.buf[4:8], uint32(z.ModTime.Unix()))
}
if z.level == BestCompression {
z.buf[8] = 2
} else if z.level == BestSpeed {
z.buf[8] = 4
}
z.buf[9] = z.OS
_, z.err = z.w.Write(z.buf[:10])
if z.err != nil {
return 0, z.err
}
if z.Extra != nil {
z.err = z.writeBytes(z.Extra)
if z.err != nil {
return 0, z.err
}
}
if z.Name != "" {
z.err = z.writeString(z.Name)
if z.err != nil {
return 0, z.err
}
}
if z.Comment != "" {
z.err = z.writeString(z.Comment)
if z.err != nil {
return 0, z.err
}
}
if z.compressor == nil {
z.compressor, _ = flate.NewWriter(z.w, z.level)
}
}
z.size += uint32(len(p))
z.digest = crc32.Update(z.digest, crc32.IEEETable, p)
n, z.err = z.compressor.Write(p)
return n, z.err
}

Write 方法的具体流程是这样的:我们先检测是否已写入元数据,若没有,则写入元数据。在写入元数据时,我们调用了 writeByteswriteString 方法实现不同类型元数据的写入。除此之外,我们还调用 flate.NewWriter 方法对 compressor 进行了初始化。最后,我们调用 compressor.Write 方法实现对数据的压缩。

辅助函数

正如我们前面提及到,我们在 Write 方法中使用了 writeByteswriteString 两个辅助函数

writeBytes 函数中,我们先对输入数据的长度进行了合法性检测,随后使用 le 大小端输入工具,将数据长度写入至缓冲区 buf ,最后写入全部数据至 io.Writer

1
2
3
4
5
6
7
8
9
10
11
12
func (z *Writer) writeBytes(b []byte) error {
if len(b) > 0xffff {
return errors.New("gzip.Write: Extra data is too large")
}
le.PutUint16(z.buf[:2], uint16(len(b)))
_, err := z.w.Write(z.buf[:2])
if err != nil {
return err
}
_, err = z.w.Write(b)
return err
}

writeString 函数中,我们对输入字符串进行编码转换,随后将其内容写入至 io.Writer

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
func (z *Writer) writeString(s string) (err error) {
// GZIP stores Latin-1 strings; error if non-Latin-1; convert if non-ASCII.
needconv := false
for _, v := range s {
if v == 0 || v > 0xff {
return errors.New("gzip.Write: non-Latin-1 header string")
}
if v > 0x7f {
needconv = true
}
}
if needconv {
b := make([]byte, 0, len(s))
for _, v := range s {
b = append(b, byte(v))
}
_, err = z.w.Write(b)
} else {
_, err = io.WriteString(z.w, s)
}
if err != nil {
return err
}
// GZIP strings are NUL-terminated.
z.buf[0] = 0
_, err = z.w.Write(z.buf[:1])
return err
}

数据落地

在调用 Write 方法后,我们需要使用 Flush 方法,将 compressor 内的压缩数据进行落地处理(写入至 io.Writer )。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func (z *Writer) Flush() error {
if z.err != nil {
return z.err
}
if z.closed {
return nil
}
if !z.wroteHeader {
z.Write(nil)
if z.err != nil {
return z.err
}
}
z.err = z.compressor.Flush()
return z.err
}

关闭实例

在完成数据压缩工作后,我们可调用 Close 方法关闭压缩器实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func (z *Writer) Close() error {
if z.err != nil {
return z.err
}
if z.closed {
return nil
}
z.closed = true
if !z.wroteHeader {
z.Write(nil)
if z.err != nil {
return z.err
}
}
z.err = z.compressor.Close()
if z.err != nil {
return z.err
}
le.PutUint32(z.buf[:4], z.digest)
le.PutUint32(z.buf[4:8], z.size)
_, z.err = z.w.Write(z.buf[:8])
return z.err
}

解压缩

有了上述对压缩代码的分析,分析解压缩代码变得轻松许多。Golang 官方在 gunzip.go 实现了解压缩算法。

在该文件中,定义了 Reader 结构体,其中的 decompressor 实现了解压缩算法的核心逻辑。

1
2
3
4
5
6
7
8
9
10
type Reader struct {
Header // valid after NewReader or Reader.Reset
r flate.Reader
decompressor io.ReadCloser
digest uint32 // CRC-32, IEEE polynomial (section 8)
size uint32 // Uncompressed size (section 2.3.1)
buf [512]byte
err error
multistream bool
}

由于篇幅限制,我们在这里跳过对解压缩实例的创建代码的分析(与创建压缩器实例的过程大同小异),我们重点关注 Read 函数的实现。

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
func (z *Reader) Read(p []byte) (n int, err error) {
if z.err != nil {
return 0, z.err
}

n, z.err = z.decompressor.Read(p)
z.digest = crc32.Update(z.digest, crc32.IEEETable, p[:n])
z.size += uint32(n)
if z.err != io.EOF {
// In the normal case we return here.
return n, z.err
}

// Finished file; check checksum and size.
if _, err := io.ReadFull(z.r, z.buf[:8]); err != nil {
z.err = noEOF(err)
return n, z.err
}
digest := le.Uint32(z.buf[:4])
size := le.Uint32(z.buf[4:8])
if digest != z.digest || size != z.size {
z.err = ErrChecksum
return n, z.err
}
z.digest, z.size = 0, 0

// File is ok; check if there is another.
if !z.multistream {
return n, io.EOF
}
z.err = nil // Remove io.EOF

if _, z.err = z.readHeader(); z.err != nil {
return n, z.err
}

// Read from next file, if necessary.
if n > 0 {
return n, nil
}
return z.Read(p)
}

Read 函数中,我们先调用 decompressor.Read 方法对数据进行解压,随后进行检验,最后我们根据元数据对数据进行复原(readHeader)。

CATALOG
  1. 1. GZIP
  2. 2. 压缩
    1. 2.1. 核心原理
    2. 2.2. 相关定义
    3. 2.3. 创建实例
    4. 2.4. 压缩流程
      1. 2.4.1. 辅助函数
    5. 2.5. 数据落地
    6. 2.6. 关闭实例
  3. 3. 解压缩