gunzip核心机制详解

输入系统的智能缓冲

GZIP解压缩采用高效的输入缓冲机制：

#define NEXTBYTE() ({ int v = get_byte(); if (v < 0) goto underrun; (uch)v; })
#define get_byte() (inptr < insize ? inbuf[inptr++] : fill_inbuf())

这套机制的精妙之处在于：

• 懒加载策略：只在需要时才填充缓冲区，减少内存占用
• 错误处理集成：数据不足时通过goto语句统一处理，保证代码健壮性

内存管理的原子性保证

在资源受限的环境中，内存管理至关重要：

static void gzip_mark(void **ptr) { *ptr = (void *) free_mem_ptr; }
static void gzip_release(void **ptr) { free_mem_ptr = (long) *ptr; }

• 资源隔离：每个压缩块拥有独立的内存分配范围
• 原子性操作：块处理要么完全成功，要么彻底回滚，避免内存泄漏
• 简单高效：避免复杂的malloc/free操作，适合嵌入式环境

DEFLATE块处理的多样性

DEFLATE格式支持三种不同类型的压缩块，每种都有独特的处理策略：

块类型	处理函数	特点	适用场景
未压缩块	inflate_stored	直接存储，无压缩	已经压缩或随机数据
固定霍夫曼块	inflate_fixed	预定义编码表	常规文本数据
动态霍夫曼块	inflate_dynamic	自定义编码表	最优压缩效果

比特流处理的精密操作

DEFLATE格式的比特对齐特性要求精细的比特级操作：

#define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}

• 批量读取：一次性读取多个字节到比特缓冲区，减少I/O操作
• 按需消费：从缓冲区中精确提取所需比特数，支持变长编码
• 状态维护：实时跟踪缓冲区中的剩余比特数，确保数据一致性

技术影响与启示

GZIP解压缩算法的成功不仅在于其技术优越性，更在于其设计理念的普适性：

• 标准化的重要性：严格的格式规范确保了跨平台兼容性
• 算法组合的威力：LZ77与霍夫曼编码的结合产生了1+1>2的效果
• 工程实践的典范：在性能、资源占用和代码可维护性之间取得完美平衡

这套解压缩机制至今仍在无数系统中稳定运行，从Linux内核启动到Web内容传输，从软件包管理到数据备份，其设计思想和实现技巧值得我们深入学习和借鉴

gzip 格式解压缩gunzip

static int INIT gunzip(void)
{
    uch flags;
    unsigned char magic[2]; /* magic header */
    char method;
    ulg orig_crc = 0;       /* original crc */
    ulg orig_len = 0;       /* original uncompressed length */
    int res;

    magic[0] = NEXTBYTE();
    magic[1] = NEXTBYTE();
    method   = NEXTBYTE();

    if (magic[0] != 037 ||
	((magic[1] != 0213) && (magic[1] != 0236))) {
	    error("bad gzip magic numbers");
	    return -1;
    }

    /* We only support method #8, DEFLATED */
    if (method != 8)  {
	    error("internal error, invalid method");
	    return -1;
    }

    flags  = (uch)get_byte();
    if ((flags & ENCRYPTED) != 0) {
	    error("Input is encrypted");
	    return -1;
    }
    if ((flags & CONTINUATION) != 0) {
	    error("Multi part input");
	    return -1;
    }
    if ((flags & RESERVED) != 0) {
	    error("Input has invalid flags");
	    return -1;
    }
    NEXTBYTE();	/* Get timestamp */
    NEXTBYTE();
    NEXTBYTE();
    NEXTBYTE();

    (void)NEXTBYTE();  /* Ignore extra flags for the moment */
    (void)NEXTBYTE();  /* Ignore OS type for the moment */

    if ((flags & EXTRA_FIELD) != 0) {
	    unsigned len = (unsigned)NEXTBYTE();
	    len |= ((unsigned)NEXTBYTE())<<8;
	    while (len--) (void)NEXTBYTE();
    }

    /* Get original file name if it was truncated */
    if ((flags & ORIG_NAME) != 0) {
	    /* Discard the old name */
	    while (NEXTBYTE() != 0) /* null */ ;
    } 

    /* Discard file comment if any */
    if ((flags & COMMENT) != 0) {
	    while (NEXTBYTE() != 0) /* null */ ;
    }

    /* Decompress */
    if ((res = inflate())) {
	    switch (res) {
	    case 0:
		    break;
	    case 1:
		    error("invalid compressed format (err=1)");
		    break;
	    case 2:
		    error("invalid compressed format (err=2)");
		    break;
	    case 3:
		    error("out of memory");
		    break;
	    case 4:
		    error("out of input data");
		    break;
	    default:
		    error("invalid compressed format (other)");
	    }
	    return -1;
    }
	    
    /* Get the crc and original length */
    /* crc32  (see algorithm.doc)
     * uncompressed input size modulo 2^32
     */
    orig_crc = (ulg) NEXTBYTE();
    orig_crc |= (ulg) NEXTBYTE() << 8;
    orig_crc |= (ulg) NEXTBYTE() << 16;
    orig_crc |= (ulg) NEXTBYTE() << 24;
    
    orig_len = (ulg) NEXTBYTE();
    orig_len |= (ulg) NEXTBYTE() << 8;
    orig_len |= (ulg) NEXTBYTE() << 16;
    orig_len |= (ulg) NEXTBYTE() << 24;
    
    /* Validate decompression */
    if (orig_crc != CRC_VALUE) {
	    error("crc error");
	    return -1;
    }
    if (orig_len != bytes_out) {
	    error("length error");
	    return -1;
    }
    return 0;

 underrun:			/* NEXTBYTE() goto's here if needed */
    error("out of input data");
    return -1;
}

函数功能概述

这是一个完整的 gzip 格式解压缩函数，负责解析 gzip 文件头、解压数据，并验证 CRC 校验和和文件长度

代码详细分析

1. 变量声明和初始化

static int INIT gunzip(void)
{
    uch flags;
    unsigned char magic[2]; /* magic header */
    char method;
    ulg orig_crc = 0;       /* original crc */
    ulg orig_len = 0;       /* original uncompressed length */
    int res;

• 定义了处理 gzip 头所需的各种变量

2. 魔术字检查

magic[0] = NEXTBYTE();
magic[1] = NEXTBYTE();
method   = NEXTBYTE();

if (magic[0] != 037 ||
    ((magic[1] != 0213) && (magic[1] != 0236))) {
        error("bad gzip magic numbers");
        return -1;
}

• 读取前3个字节：2字节魔术字和1字节压缩方法
• 检查魔术字：第一个字节必须是八进制的 037(0x1F)，第二个字节必须是 0213(0x8B) 或 0236(0x9E)

3. 压缩方法验证

/* We only support method #8, DEFLATED */
if (method != 8)  {
        error("internal error, invalid method");
        return -1;
}

• 只支持 DEFLATE 压缩算法（方法编号为8）
• DEFLATE = LZ77 + 霍夫曼编码
  • LZ77 算法（字典编码）: 用指向之前出现过的相同数据的引用来替换重复的数据片段
  • 霍夫曼编码: 给出现频率高的符号分配短的编码，给出现频率低的符号分配长的编码

4. 标志位处理

flags  = (uch)get_byte();
if ((flags & ENCRYPTED) != 0) {
        error("Input is encrypted");
        return -1;
}
if ((flags & CONTINUATION) != 0) {
        error("Multi part input");
        return -1;
}
if ((flags & RESERVED) != 0) {
        error("Input has invalid flags");
        return -1;
}

• 读取标志位字节
• 检查不支持的特性：
  • 加密文件（不支持）
  • 多部分文件（不支持）
  • 保留位（不支持）

5. 跳过时间戳和额外信息

NEXTBYTE();	/* Get timestamp */
NEXTBYTE();
NEXTBYTE();
NEXTBYTE();

(void)NEXTBYTE();  /* Ignore extra flags for the moment */
(void)NEXTBYTE();  /* Ignore OS type for the moment */

• 跳过4字节的时间戳（文件修改时间）
• 跳过1字节的额外标志
• 跳过1字节的操作系统类型

6. 处理额外字段

if ((flags & EXTRA_FIELD) != 0) {
        unsigned len = (unsigned)NEXTBYTE();
        len |= ((unsigned)NEXTBYTE())<<8;
        while (len--) (void)NEXTBYTE();
}

• 如果存在额外字段，读取其长度（2字节，小端序）
• 跳过整个额外字段的内容

7. 处理文件名

/* Get original file name if it was truncated */
if ((flags & ORIG_NAME) != 0) {
        /* Discard the old name */
        while (NEXTBYTE() != 0) /* null */ ;
}

• 如果存在原始文件名，读取直到遇到空字符（0x00）
• 只是读取并丢弃，不保存文件名

8. 处理注释

/* Discard file comment if any */
if ((flags & COMMENT) != 0) {
        while (NEXTBYTE() != 0) /* null */ ;
}

• 如果存在注释，同样读取直到空字符并丢弃

9. 核心解压过程

/* Decompress */
if ((res = inflate())) {
        switch (res) {
        case 0:
                break;
        case 1:
                error("invalid compressed format (err=1)");
                break;
        case 2:
                error("invalid compressed format (err=2)");
                break;
        case 3:
                error("out of memory");
                break;
        case 4:
                error("out of input data");
                break;
        default:
                error("invalid compressed format (other)");
        }
        return -1;
}

• 调用 inflate() 函数进行实际的 DEFLATE 解压缩
• 处理各种可能的错误：
  • 1,2：压缩格式错误
  • 3：内存不足
  • 4：输入数据不足
  • 其他：未知错误

10. 读取校验信息

/* Get the crc and original length */
/* crc32  (see algorithm.doc)
 * uncompressed input size modulo 2^32
 */
orig_crc = (ulg) NEXTBYTE();
orig_crc |= (ulg) NEXTBYTE() << 8;
orig_crc |= (ulg) NEXTBYTE() << 16;
orig_crc |= (ulg) NEXTBYTE() << 24;

orig_len = (ulg) NEXTBYTE();
orig_len |= (ulg) NEXTBYTE() << 8;
orig_len |= (ulg) NEXTBYTE() << 16;
orig_len |= (ulg) NEXTBYTE() << 24;

• 读取4字节的 CRC32 校验和（小端序）
• 读取4字节的原始文件长度（小端序）

11. 完整性验证

/* Validate decompression */
if (orig_crc != CRC_VALUE) {
        error("crc error");
        return -1;
}
if (orig_len != bytes_out) {
        error("length error");
        return -1;
}
return 0;

• 比较解压数据的 CRC 值与文件头中的 CRC 值
• 比较解压出的数据长度与文件头中的原始长度
• 两者都匹配则返回成功（0）

12. 错误处理

underrun:			/* NEXTBYTE() goto's here if needed */
error("out of input data");
return -1;

• 处理输入数据不足的情况（NEXTBYTE() 在无法读取时跳转到这里）

函数功能总结

主要功能：完整的 gzip 格式解压缩实现

处理流程：

1. 文件头解析 - 验证魔术字、压缩方法、标志位
2. 元数据处理 - 跳过时间戳、额外字段、文件名、注释等
3. 数据解压 - 调用 DEFLATE 解压算法
4. 完整性验证 - 检查 CRC32 校验和和文件长度

输入数据读取NEXTBYTE

#define NEXTBYTE()  ({ int v = get_byte(); if (v < 0) goto underrun; (uch)v; })
#define get_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf())
static int fill_inbuf(void)
{
	if (insize != 0) {
		error("ran out of input data");
	}

	inbuf = input_data;
	insize = input_len;
	inptr = 1;
	return inbuf[0];
}

代码详细分析

1. NEXTBYTE 宏

#define NEXTBYTE()  ({ int v = get_byte(); if (v < 0) goto underrun; (uch)v; })

分解执行流程：

1. int v = get_byte(); - 调用 get_byte() 获取一个字节
2. if (v < 0) goto underrun; - 如果返回值小于0，表示数据不足，跳转到 underrun 标签
3. (uch)v; - 将结果转换为无符号字符类型并作为宏的返回值

2. get_byte 宏

#define get_byte()  (inptr < insize ? inbuf[inptr++] : fill_inbuf())

逻辑分析：

• inptr < insize - 检查当前读取位置是否在数据范围内
• 如果为真：inbuf[inptr++] - 从缓冲区读取当前字节，并递增指针
• 如果为假：fill_inbuf() - 调用函数重新填充输入缓冲区

工作方式：

• 当还有数据时，直接从内存缓冲区读取（快速）
• 当数据用完时，调用函数重新填充缓冲区

3. fill_inbuf 函数

static int fill_inbuf(void)
{
	if (insize != 0) {
		error("ran out of input data");
	}

	inbuf = input_data;
	insize = input_len;
	inptr = 1;
	return inbuf[0];
}

错误检查

if (insize != 0) {
	error("ran out of input data");
}

• 检查 insize 是否不为0
• 如果不为0，说明之前已经填充过数据
• 这个检查确保不会意外重复填充缓冲区

缓冲区初始化

inbuf = input_data;
insize = input_len;
inptr = 1;

• inbuf = input_data; - 将输入缓冲区指向全局的压缩数据
• insize = input_len; - 设置缓冲区大小为全局的输入数据长度
• inptr = 1; - 将读取指针设置为1

返回数据

return inbuf[0];

• 返回缓冲区第一个字节（索引0）
• 由于 inptr 被设置为1，下次调用 get_byte() 将从索引1开始读取

全局变量说明

• inbuf - 当前输入缓冲区指针
• insize - 当前缓冲区中剩余的数据大小
• inptr - 当前读取位置（索引）
• input_data - 原始的压缩数据指针
• input_len - 原始压缩数据的总长度

DEFLATE 解压缩inflate

STATIC int INIT inflate(void)
/* decompress an inflated entry */
{
  int e;                /* last block flag */
  int r;                /* result code */
  unsigned h;           /* maximum struct huft's malloc'ed */
  void *ptr;

  /* initialize window, bit buffer */
  wp = 0;
  bk = 0;
  bb = 0;


  /* decompress until the last block */
  h = 0;
  do {
    hufts = 0;
    gzip_mark(&ptr);
    if ((r = inflate_block(&e)) != 0) {
      gzip_release(&ptr);	    
      return r;
    }
    gzip_release(&ptr);
    if (hufts > h)
      h = hufts;
  } while (!e);

  /* Undo too much lookahead. The next read will be byte aligned so we
   * can discard unused bits in the last meaningful byte.
   */
  while (bk >= 8) {
    bk -= 8;
    inptr--;
  }

  /* flush out slide */
  flush_output(wp);


  /* return success */
#ifdef DEBUG
  fprintf(stderr, "<%u> ", h);
#endif /* DEBUG */
  return 0;
}

函数功能概述

这是 DEFLATE 压缩格式的解压主函数，负责协调整个解压流程，包括块处理、比特流管理和输出缓冲

代码详细分析

1. 变量声明和初始化

STATIC int INIT inflate(void)
/* decompress an inflated entry */
{
  int e;                /* last block flag */
  int r;                /* result code */
  unsigned h;           /* maximum struct huft's malloc'ed */
  void *ptr;

  /* initialize window, bit buffer */
  wp = 0;
  bk = 0;
  bb = 0;

变量说明：

• e - 最后块标志，标记是否是最后一个压缩块
• r - 操作结果代码，用于错误处理
• h - 霍夫曼树节点的最大分配数量
• ptr - 内存管理指针

缓冲区初始化：

• wp = 0; - 窗口写入位置指针归零
• bk = 0; - 比特缓冲区中有效比特数归零
• bb = 0; - 比特缓冲区内容归零

这些全局变量维护解压状态：

• wp - 输出窗口的当前写入位置
• bk - 当前比特缓冲区中未处理的比特数
• bb - 存储从输入流读取的比特数据

2. 主解压循环

  /* decompress until the last block */
  h = 0;
  do {
    hufts = 0;
    gzip_mark(&ptr);
    if ((r = inflate_block(&e)) != 0) {
      gzip_release(&ptr);	    
      return r;
    }
    gzip_release(&ptr);
    if (hufts > h)
      h = hufts;
  } while (!e);

初始化：

h = 0;

• 初始化最大霍夫曼树节点计数器

循环开始：

do {
    hufts = 0;
    gzip_mark(&ptr);

• hufts = 0; - 重置当前块的霍夫曼树节点计数器
• gzip_mark(&ptr); - 标记内存分配状态，用于后续清理

块解压：

    if ((r = inflate_block(&e)) != 0) {
      gzip_release(&ptr);	    
      return r;
    }

• 调用 inflate_block(&e) 解压单个 DEFLATE 块
• 如果返回非零值（错误），释放内存并返回错误代码
• e 参数用于接收"是否是最后块"的标志

内存管理和统计：

    gzip_release(&ptr);
    if (hufts > h)
      h = hufts;

• gzip_release(&ptr); - 释放当前块分配的内存
• 更新最大霍夫曼树节点计数

循环条件：

  } while (!e);

• 继续循环直到遇到最后一个块（e != 0）

3. 比特流清理

  /* Undo too much lookahead. The next read will be byte aligned so we
   * can discard unused bits in the last meaningful byte.
   */
  while (bk >= 8) {
    bk -= 8;
    inptr--;
  }

• 回退因比特预读而多读取的字节，确保输入指针正确指向最后一个有意义的字节边界

具体操作：

• while (bk >= 8) - 如果比特缓冲区中剩余超过8个比特（1字节）
• bk -= 8; - 减少比特计数
• inptr--; - 回退输入指针，丢弃未使用的字节

DEFLATE 的比特流特性

• DEFLATE 压缩格式是比特对齐的，而不是字节对齐的。这意味着：

• 数据可以跨字节边界存储

• 一个符号可能从某个字节的中间开始，延续到下一个字节

• 解压器需要以比特为单位读取数据

预读（Lookahead）机制

• 在解压过程中，为了高效读取比特流，代码会：

• 批量读取：一次读取多个字节到比特缓冲区

• 比特级消费：从缓冲区中按需提取特定数量的比特

• 缓冲区补充：当缓冲区比特不足时，读取更多字节

产生多余读取的原因

• 解压器无法预先知道需要多少比特
• 为了效率，会预先填充缓冲区
• 解压结束后，缓冲区中可能残留未使用的比特

4. 输出处理

  /* flush out slide */
  flush_output(wp);

• 将输出窗口中的数据刷新到最终输出
• wp 是当前输出窗口的写入位置
• 确保所有解压的数据都被正确处理和输出

5. 返回成功

  /* return success */
#ifdef DEBUG
  fprintf(stderr, "<%u> ", h);
#endif /* DEBUG */
  return 0;
}

• 在调试模式下输出最大霍夫曼树节点使用量
• 返回 0 表示解压成功完成

函数功能总结

主要功能：DEFLATE 压缩格式的完整解压实现

关键特性：

• 增量处理：支持流式解压，无需一次性加载全部数据
• 错误恢复：完善的错误检测和清理机制
• 内存效率：及时释放不再需要的资源
• 比特精确：正确处理比特级的数据读取

内存管理函数gzip_mark和gzip_release

static void gzip_mark(void **ptr)
{
	*ptr = (void *) free_mem_ptr;
}

static void gzip_release(void **ptr)
{
	free_mem_ptr = (long) *ptr;
}

函数功能分析

1. gzip_mark 函数

static void gzip_mark(void **ptr)
{
	*ptr = (void *) free_mem_ptr;
}

功能：保存当前内存分配位置

参数：

• void **ptr - 二级指针，用于存储当前的内存位置

操作：

• *ptr = (void *) free_mem_ptr;
• 将 free_mem_ptr 的当前值保存到 ptr 指向的位置
• 相当于给当前内存分配状态拍个"快照"

2. gzip_release 函数

static void gzip_release(void **ptr)
{
	free_mem_ptr = (long) *ptr;
}

功能：恢复到之前保存的内存位置

参数：

• void **ptr - 二级指针，指向之前保存的内存位置

操作：

• free_mem_ptr = (long) *ptr;
• 将 free_mem_ptr 设置回之前保存的位置
• 相当于"回滚"到标记时的内存状态

工作原理图示

内存指针变化示例

// 初始状态
free_mem_ptr = 0x1000  // 假设&end的地址

// 开始处理一个块
void *saved_ptr;
gzip_mark(&saved_ptr);  // saved_ptr = 0x1000

// 在inflate_block中分配霍夫曼树
// free_mem_ptr 增加到 0x1100

// 解压成功，释放内存
gzip_release(&saved_ptr);  // free_mem_ptr = 0x1000

这种设计的好处

1. 内存池管理

• 使用简单的指针递增来分配内存
• 避免复杂的 malloc/free 操作
• 在资源受限环境中特别有效

2. 原子性操作

每个块的处理是原子的：

• 要么整个块成功，内存被回收
• 要么失败，所有分配的内存都被释放

解压单个 DEFLATE 压缩块inflate_block

STATIC int INIT inflate_block(
	int *e                  /* last block flag */
	)
/* decompress an inflated block */
{
  unsigned t;           /* block type */
  register ulg b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */

  DEBG("<blk");

  /* make local bit buffer */
  b = bb;
  k = bk;


  /* read in last block bit */
  NEEDBITS(1)
  *e = (int)b & 1;
  DUMPBITS(1)


  /* read in block type */
  NEEDBITS(2)
  t = (unsigned)b & 3;
  DUMPBITS(2)


  /* restore the global bit buffer */
  bb = b;
  bk = k;

  /* inflate that block type */
  if (t == 2)
    return inflate_dynamic();
  if (t == 0)
    return inflate_stored();
  if (t == 1)
    return inflate_fixed();

  DEBG(">");

  /* bad block type */
  return 2;

 underrun:
  return 4;			/* Input underrun */
}

函数功能概述

这个函数负责解压单个 DEFLATE 压缩块，识别块类型并分发给相应的解压例程

代码详细分析

1. 函数声明和变量定义

STATIC int INIT inflate_block(
	int *e                  /* last block flag */
	)
/* decompress an inflated block */
{
  unsigned t;           /* block type */
  register ulg b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */

  DEBG("<blk");

参数说明：

• int *e - 输出参数，用于返回是否是最后一个块

局部变量：

• t - 块类型
• b - 本地比特缓冲区（寄存器变量，提高访问速度）
• k - 本地比特计数（寄存器变量）

2. 初始化本地比特缓冲区

  /* make local bit buffer */
  b = bb;
  k = bk;

• 将全局比特缓冲区状态复制到局部变量
• bb - 全局比特缓冲区内容
• bk - 全局比特缓冲区中有效比特数
• 使用局部变量避免频繁访问全局变量，提高性能

3. 读取最后块标志

  /* read in last block bit */
  NEEDBITS(1)
  *e = (int)b & 1;
  DUMPBITS(1)

宏展开分析：
NEEDBITS(1) 可能展开为：

while (k < 1) {
    b |= (ulg)NEXTBYTE() << k;
    k += 8;
}

• NEEDBITS(1) - 确保缓冲区中至少有1个比特可用
• *e = (int)b & 1; - 提取最低比特作为最后块标志
  • 0 - 还有更多块
  • 1 - 这是最后一个块
• DUMPBITS(1) - 消费掉这1个比特

4. 读取块类型

  /* read in block type */
  NEEDBITS(2)
  t = (unsigned)b & 3;
  DUMPBITS(2)

• NEEDBITS(2) - 确保缓冲区中至少有2个比特可用
• t = (unsigned)b & 3; - 提取最低2个比特作为块类型
  • 二进制 & 11（十进制3）获取最后2位
• DUMPBITS(2) - 消费掉这2个比特

DEFLATE 块类型：

• 0 (00) - 未压缩块
• 1 (01) - 固定霍夫曼编码块
• 2 (10) - 动态霍夫曼编码块
• 3 (11) - 保留（错误）

5. 恢复全局比特缓冲区

  /* restore the global bit buffer */
  bb = b;
  bk = k;

• 将更新后的比特缓冲区状态写回全局变量
• 由于读取了3个比特（1+2），b 和 k 已经更新
• 后续的解压函数需要正确的比特缓冲区状态

6. 块类型分发处理

  /* inflate that block type */
  if (t == 2)
    return inflate_dynamic();
  if (t == 0)
    return inflate_stored();
  if (t == 1)
    return inflate_fixed();

  DEBG(">");

1. t == 2 - 动态霍夫曼编码块，调用 inflate_dynamic()
   • 最复杂的类型，块头包含霍夫曼树定义
2. t == 0 - 未压缩块，调用 inflate_stored()
   • 最简单的类型，直接存储原始数据
3. t == 1 - 固定霍夫曼编码块，调用 inflate_fixed()
   • 使用预定义的霍夫曼编码

7. 错误处理

  /* bad block type */
  return 2;

 underrun:
  return 4;			/* Input underrun */
}

错误返回码：

• return 2 - 无效的块类型（类型3）
• return 4 - 输入数据不足（从 underrun 标签跳转）

underrun 标签：

• 由 NEEDBITS 宏在数据不足时跳转到这里
• 表示需要更多数据但输入已耗尽

函数功能总结

主要功能：DEFLATE 压缩块的类型识别和分发

核心职责：

1. 块头解析

   • 读取最后块标志
   • 读取块类型标识
   • 验证块类型有效性

2. 任务分发

   • 根据块类型调用相应的解压例程
   • 传递正确的比特缓冲区状态

DEFLATE 块类型处理：

类型	值	处理函数	特点
未压缩	0	inflate_stored	直接存储，无压缩
固定霍夫曼	1	inflate_fixed	预定义编码表
动态霍夫曼	2	inflate_dynamic	自定义编码表
保留	3	错误	无效类型

输出窗口刷新flush_output

#define wp outcnt
#define flush_output(w) (wp=(w),flush_window())
static void flush_window_low(void)
{
    ulg c = crc;         /* temporary variable */
    unsigned n;
    uch *in, *out, ch;
    
    in = window;
    out = &output_data[output_ptr]; 
    for (n = 0; n < outcnt; n++) {
	    ch = *out++ = *in++;
	    c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
    }
    crc = c;
    bytes_out += (ulg)outcnt;
    output_ptr += (ulg)outcnt;
    outcnt = 0;
}

static void flush_window_high(void)
{
    ulg c = crc;         /* temporary variable */
    unsigned n;
    uch *in,  ch;
    in = window;
    for (n = 0; n < outcnt; n++) {
	ch = *output_data++ = *in++;
	if ((ulg)output_data == low_buffer_end) output_data=high_buffer_start;
	c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
    }
    crc = c;
    bytes_out += (ulg)outcnt;
    outcnt = 0;
}

static void flush_window(void)
{
	if (high_loaded) flush_window_high();
	else flush_window_low();
}

宏定义和函数概述

1. 宏定义

#define wp outcnt
#define flush_output(w) (wp=(w),flush_window())

wp 宏：

• wp 是 outcnt 的别名
• outcnt 表示输出窗口中待刷新数据的字节数

flush_output(w) 宏：

• wp=(w) - 设置输出计数为参数 w 的值
• flush_window() - 调用刷新函数
• 这是一个逗号表达式，依次执行两个操作

flush_window_low 函数（低内存模式）

1. 变量声明和初始化

static void flush_window_low(void)
{
    ulg c = crc;         /* temporary variable */
    unsigned n;
    uch *in, *out, ch;
    
    in = window;
    out = &output_data[output_ptr]; 

变量说明：

• c = crc - 保存当前 CRC 值的临时变量
• n - 循环计数器
• in - 输入指针，指向窗口数据
• out - 输出指针，指向输出缓冲区当前位置
• ch - 临时字节变量

指针初始化：

• in = window - 输入指向解压窗口开始位置
• out = &output_data[output_ptr] - 输出指向输出缓冲区的当前写入位置

2. 数据复制和 CRC 计算循环

    for (n = 0; n < outcnt; n++) {
	    ch = *out++ = *in++;
	    c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
    }

循环操作：

• n = 0; n < outcnt; n++ - 遍历所有待输出字节
• ch = *out++ = *in++ - 从窗口复制到输出缓冲区，同时移动两个指针
• CRC 计算：c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8)
  • ((int)c ^ ch) & 0xff - 当前 CRC 与字节异或，取低8位
  • crc_32_tab[...] - 查表获取新的 CRC 部分
  • ^ (c >> 8) - 与右移8位的原 CRC 异或

3. 状态更新

    crc = c;
    bytes_out += (ulg)outcnt;
    output_ptr += (ulg)outcnt;
    outcnt = 0;

更新操作：

• crc = c - 保存更新后的 CRC 值
• bytes_out += (ulg)outcnt - 增加总输出字节计数
• output_ptr += (ulg)outcnt - 移动输出缓冲区指针
• outcnt = 0 - 重置输出计数，窗口为空

flush_window_high 函数（高内存模式）

1. 变量声明和初始化

static void flush_window_high(void)
{
    ulg c = crc;         /* temporary variable */
    unsigned n;
    uch *in,  ch;
    in = window;

与低内存模式的区别：

• 没有 out 指针，使用全局 output_data 指针
• 支持环形缓冲区回绕

2. 数据复制和缓冲区管理

    for (n = 0; n < outcnt; n++) {
	ch = *output_data++ = *in++;
	if ((ulg)output_data == low_buffer_end) output_data=high_buffer_start;
	c = crc_32_tab[((int)c ^ ch) & 0xff] ^ (c >> 8);
    }

特殊处理：

• ch = *output_data++ = *in++ - 直接使用全局输出指针
• if ((ulg)output_data == low_buffer_end) - 检查是否到达缓冲区末端
• output_data=high_buffer_start - 如果到达末端，回绕到高端缓冲区开始

3. 状态更新

    crc = c;
    bytes_out += (ulg)outcnt;
    outcnt = 0;

与低内存模式的区别：

• 不更新 output_ptr，因为使用全局 output_data 指针
• 其他更新相同

flush_window 分发函数

static void flush_window(void)
{
	if (high_loaded) flush_window_high();
	else flush_window_low();
}

条件分发：

• high_loaded - 标志是否使用高内存模式
• 根据系统内存配置选择适当的刷新策略

函数功能总结

主要功能：将解压窗口中的数据刷新到输出缓冲区，并更新相关状态

核心职责：

1. 数据转移

   • 从解压窗口复制数据到输出缓冲区
   • 支持不同的内存管理模式
   • 处理环形缓冲区回绕

2. 完整性验证

   • 实时计算 CRC32 校验和
   • 使用查表法优化计算速度

3. 内存适配

   • 低内存模式：简单的线性缓冲区
   • 高内存模式：复杂的环形缓冲区管理
   • 根据系统资源自动选择策略

关键数据结构：

• window[] - 解压输出窗口
• output_data - 最终输出缓冲区
• outcnt - 窗口中待刷新字节数
• crc - 循环冗余校验值
• bytes_out - 总解压字节数

生成CRC32查找表makecrc

static void INIT
makecrc(void)
{
/* Not copyrighted 1990 Mark Adler	*/

  unsigned long c;      /* crc shift register */
  unsigned long e;      /* polynomial exclusive-or pattern */
  int i;                /* counter for all possible eight bit values */
  int k;                /* byte being shifted into crc apparatus */

  /* terms of polynomial defining this crc (except x^32): */
  static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

  /* Make exclusive-or pattern from polynomial */
  e = 0;
  for (i = 0; i < sizeof(p)/sizeof(int); i++)
    e |= 1L << (31 - p[i]);

  crc_32_tab[0] = 0;

  for (i = 1; i < 256; i++)
  {
    c = 0;
    for (k = i | 256; k != 1; k >>= 1)
    {
      c = c & 1 ? (c >> 1) ^ e : c >> 1;
      if (k & 1)
        c ^= e;
    }
    crc_32_tab[i] = c;
  }

  /* this is initialized here so this code could reside in ROM */
  crc = (ulg)0xffffffffUL; /* shift register contents */
}

函数功能概述

这是一个用于生成CRC32查找表的函数，采用位运算方法预先计算所有256个可能字节值的CRC32结果，存储在全局数组crc_32_tab中

代码逐段解析

函数定义和变量声明

static void INIT
makecrc(void)
{
/* Not copyrighted 1990 Mark Adler	*/

  unsigned long c;      /* crc shift register */
  unsigned long e;      /* polynomial exclusive-or pattern */
  int i;                /* counter for all possible eight bit values */
  int k;                /* byte being shifted into crc apparatus */

• static void INIT makecrc(void): 静态函数
• unsigned long c: 用于计算过程中的临时存储
• unsigned long e: 多项式异或模式，代表CRC32多项式
• int i: 循环计数器，用于0-255的所有字节值
• int k: 当前正在处理的字节

CRC32多项式定义

  /* terms of polynomial defining this crc (except x^32): */
  static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};

• 定义CRC32多项式的各项指数（除了x³²项）
• 这是标准的IEEE 802.3 CRC32多项式：
  x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1
• 数组中的数字对应多项式各项的指数（从右向左）

生成多项式异或模式

  /* Make exclusive-or pattern from polynomial */
  e = 0;
  for (i = 0; i < sizeof(p)/sizeof(int); i++)
    e |= 1L << (31 - p[i]);

• e = 0: 初始化多项式模式为0
• sizeof(p)/sizeof(int): 计算多项式项数（14项）
• e |= 1L << (31 - p[i]): 为每个多项式项设置对应的位
  • 1L << (31 - p[i]): 将1左移(31-指数)位
• 最终e包含多项式所有的位模式

初始化CRC表首元素

  crc_32_tab[0] = 0;

• 字节值为0的CRC结果就是0

主循环：计算每个字节的CRC值

  for (i = 1; i < 256; i++)
  {
    c = 0;
    for (k = i | 256; k != 1; k >>= 1)
    {
      c = c & 1 ? (c >> 1) ^ e : c >> 1;
      if (k & 1)
        c ^= e;
    }
    crc_32_tab[i] = c;
  }

外层循环

for (i = 1; i < 256; i++)

• 遍历所有可能的字节值（1-255）

内层循环初始化

c = 0;
for (k = i | 256; k != 1; k >>= 1)

• c = 0: 重置CRC寄存器
• k = i | 256: 将当前字节值与256进行或运算，确保处理9位（256提供第9位作为标志位）
• k != 1: 循环直到k右移到只剩1
• k >>= 1: 每次循环右移1位

CRC计算核心逻辑

c = c & 1 ? (c >> 1) ^ e : c >> 1;
if (k & 1)
  c ^= e;

第一行：CRC寄存器移位

• c & 1: 检查CRC寄存器最低位是否为1
• (c >> 1) ^ e: 如果最低位为1，右移后与多项式异或
• c >> 1: 如果最低位为0，直接右移

第二行：输入位处理

• k & 1: 检查当前输入位是否为1
• c ^= e: 如果输入位为1，CRC寄存器与多项式异或

存储结果

crc_32_tab[i] = c;

• 将计算出的CRC值存入查找表

初始化CRC寄存器

  /* this is initialized here so this code could reside in ROM */
  crc = (ulg)0xffffffffUL; /* shift register contents */
}

• 初始化全局CRC寄存器为0xFFFFFFFF（标准CRC32初始值）

查找表的意义

生成的crc_32_tab[256]允许后续的CRC计算使用查表法，将8位数据的CRC计算优化为单次查找操作，极大提高了计算效率