第11章：分页算法——把排好的一串块，装进一页页

换行把段落切成行，分页再把行装进页。屏幕没有无限长的一卷纸，放不下，就开新页。

11.1 问题：从"一串块"到"一页页"

回顾整条流水线：RubbishHtmlParser 解析完一章的 XHTML 后，得到一串 std::list<Block *> blocks（块，说人话：排版里的最小单元，一段文字或一张图片就是一个块）。其中 TextBlock 已经用动态规划算好了断行点（存在 line_breaks 里），ImageBlock 已经记下图片源路径。但这一串 blocks 本质上是一条"不知道尽头在哪"的长卷——它自己根本不知道会被切成几页。电子墨水屏的每一页只有固定高度 page_height（说人话：页高就是屏幕一页能放多少行内容的总高度，超出就得另起一页；由渲染器的 get_page_height() 提供）。分页（pagination，说人话：把排好的内容按一屏一屏切分开，每屏就是一页）就是把这卷长卷，裁剪成一张张固定高度的页。

分页的输出是一个 std::vector<Page *> pages。每个 Page 只回答一个问题："这一页放了哪些元素？" 而每个元素（PageElement）记录两样东西：它来自哪个 block、以及它在本页的 y_pos（纵向位置）。这里的精髓在于：分页阶段一个像素都不画，它只做"记账"——把每个行/每张图应放的位置记下来，真正的绘制留到下一章。看 lib/Epub/RubbishHtmlParser/Page.h 里的真实定义。

/* Page.h：一页 = 一串"带 y 坐标的元素" */
class PageElement {
public:
  int y_pos;                  // 元素在本页的纵向位置
  virtual void render(Renderer *renderer, Epub *epub) = 0;
};

class PageLine : public PageElement {
  TextBlock *block;            // 来自哪个文本块
  int line_break_index;      // 该块的第几行
};

class PageImage : public PageElement {
  ImageBlock *block;           // 来自哪张图片
};

class Page {
  std::vector<PageElement *> elements;   // 本页的所有元素
};

分页工作的入口是 RubbishHtmlParser::layout(renderer, epub)。它先做两件准备工作：从渲染器取行高（说人话：一行文字占多高；用页高除以行高，就能算出一页能放几行）与页高，然后让每个 block 先自己"排好版"——文本块断行、图片块缩放。注意第二个循环里的 vTaskDelay(1)：解析整章可能很耗时，每次处理一个 block 就喂一次看门狗，避免触发 FreeRTOS 看门狗复位。这是嵌入式代码里"长任务主动让出"的典型写法。

/* RubbishHtmlParser::layout —— 分页前的准备 */
const int line_height = renderer->get_line_height();   // 一行多高
const int page_height = renderer->get_page_height();  // 一页多高

for (auto block : blocks) {
  block->layout(renderer, epub);   // 文本块断行、图片块缩放
  vTaskDelay(1);                // 喂看门狗
}

11.2 块高度计算：文本行数 × 行高，图片等比缩放

要把内容装进页，第一步是知道每个元素"占多高"。文本块的高度好算：TextBlock::layout 已经在上一章量好了每个单词的宽度并算出行断点，行数就是 line_breaks.size()；再乘上行高 line_height 就是整块的高度。而行高 get_line_height() 直接来自字体的度量信息——EpdiyFrameBufferRenderer 里它等于 m_regular_font->advance_y（字体的行步进值），字间距 get_space_width() 则取空格字形 advance_x。字体是"页面的度量单位"，所有高度都从它派生。

/* EpdiyFrameBufferRenderer：行高与字间距都来自字体度量 */
int get_line_height() {
  return m_regular_font->advance_y;   // 字体的行步进 = 行高
}
int get_space_width() {
  auto space_glyph = epd_get_glyph(m_regular_font, ' ');
  return space_glyph->advance_x;     // 空格的宽度
}

图片块的高度则要"算"出来。图片的原始尺寸存在 EPUB 里，可能比屏幕还大，必须等比缩放。看 ImageBlock::layout 的真实实现：先用 get_image_size 读出原始宽高；只要任意一边超过页面，就取 min(页面宽/原宽, 页面高/原高) 作为缩放比，宽高同乘——这是"等比缩小到能放进一页"的经典做法。缩放后的 height，就是这张图在分页时占用的高度。缩小的图片不会放大，这是有意的取舍（放大无意义且费内存）。

/* ImageBlock::layout —— 读尺寸并等比缩放 */
uint8_t *image_data = epub->get_item_contents(m_src, &image_data_size);
renderer->get_image_size(m_src, image_data, image_data_size, &width, &height);

if (width > renderer->get_page_width() ||
    height > renderer->get_page_height()) {
  float scale = std::min(
      float(renderer->get_page_width()) / float(width),
      float(renderer->get_page_height()) / float(height));
  width  *= scale;
  height *= scale;
}
// 水平居中：x 位置在分页时一并算好
x_pos = (renderer->get_page_width() - width) / 2;

除了元素本身的高度，还有一块"隐性高度"：段落间距。在 layout() 的分页主循环里，每处理完一个文本块，都会在 y 上追加 line_height * 0.5——这是段与段之间留出的半行空白，让段落不会挤成一团。三类"占页量"汇总如下表。

元素	占页高度	来源
文本行	line_height	get_line_height() = m_regular_font->advance_y
段落间	line_height * 0.5	文本块结束后无条件追加半行
图片	等比缩放后的 height	ImageBlock::layout，超限才缩放

11.3 装填策略：从当前 y 开始放，放不下就开新页

准备好了高度，就可以装填（说人话：按顺序把一个个块放进当前页，这一页放不下了就另起一页再继续放）了。分页主循环非常直白：用一个 y 指针跟踪"当前页已经用掉了多少高度"，从 0 开始；对每个文本块逐行、对每张图片逐个处理——y + 元素高度 > page_height 就说明当前页放不下这个元素了，于是开一张新页并把 y 清零，再从页顶开始放。下面是 RubbishHtmlParser::layout 分页部分的完整真实代码。

/* RubbishHtmlParser::layout —— 分页主循环 */
int y = 0;
pages.push_back(new Page());              // 先开第一页
for (auto block : blocks) {
  if (block->getType() == BlockType::TEXT_BLOCK) {
    TextBlock *textBlock = (TextBlock *)block;
    for (int i = 0; i < textBlock->line_breaks.size(); i++) {
      if (y + line_height > page_height) {   // 放不下这一行了
        pages.push_back(new Page());
        y = 0;                             // 新页从顶部开始
      }
      pages.back()->elements.push_back(
          new PageLine(textBlock, i, y));  // 记下：第 i 行放在 y 处
      y += line_height;
    }
    y += line_height * 0.5;                 // 段间半行空白
  }
  if (block->getType() == BlockType::IMAGE_BLOCK) {
    ImageBlock *imageBlock = (ImageBlock *)block;
    if (y + imageBlock->height > page_height) { // 图片放不下
      pages.push_back(new Page());
      y = 0;
    }
    pages.back()->elements.push_back(new PageImage(imageBlock, y));
    y += imageBlock->height;
  }
}

这是一次贪婪的"先到先放"装填：放得下就放，放不下就翻页，绝不回头。它不做任何全局优化——不会尝试把前一页末尾的空白补满，也不会为了保持某段完整而提前换页。好处是复杂度是线性的（一次遍历、每元素 O(1)），坏处是页面边界的落点比较"粗糙"。还要注意装填的最小单位：文本按"行"装、图片按"张"装——一行文字、一张图片都是不可再拆的原子。所以页边界永远落在某两行之间，而不会切在某个词的中间。

/* 数值演算：page_height=925, line_height=28
   一页最多 = 925 / 28 = 33 行（余 1 点放不下第 34 行）
   一个 34 行的段落：
     页 0：第 1..33 行（y 从 0 累加到 33*28=924）
     第 34 行：y+28=952 > 925 → 开新页，页 1 从顶部放 1 行 */
// 于是页 0 的 924px 被用完，页 1 只放了 1 行 + 半行段距

11.4 分页的局限：够用，但糙

作者在 README 的 "How well does it work?" 一节里很坦诚地自评："The code makes no attempt to break pages at suitable places - there are hints that can be extracted from the XHTML files and there are also CSS files that could be used."——代码从不尝试在"合适的地方"断页。所谓"合适"，是指章节标题不该孤悬在页面最底一行、图片不该和它的图注分家、遇到明确的断页提示（如 XHTML 里的分页样式或 CSS 的 page-break-*）应当尊重。这些"提示"就在 XHTML 和 CSS 里，只是当前实现完全无视了它们。

最直观的"糙"是标签覆盖的取舍：解析器维护了一张跳过表 SKIP_TAGS = {"head", "table"}——表格整个被跳过，遇到 <table> 就从解析树里 return false（不深入子树）。这延续了第 9 章"极简标签"的策略：只认 p/div/li/br/h1..h6/b/i/img，其余结构要么当文本、要么直接放弃。分页层面同样如此：不做孤儿行控制、不保证"标题跟着正文走"。下表列出几处可观察到的局限与改进方向。

/* RubbishHtmlParser.cpp：被整体跳过的标签 */
const char *SKIP_TAGS[] = {"head", "table"};

if (matches(tag_name, SKIP_TAGS, NUM_SKIP_TAGS)) {
  return false;   // 不深入该子树 → 表格内容被忽略
}

局限	可观察到的现象	改进方向
不在"合适处"断页	标题/图片可能孤悬页尾	解析 XHTML 断页提示与 CSS
表格整体跳过	含 <table> 的章节内容缺失	把表格当作简单文本块
块尾半行无条件追加	每段结束都浪费半行，可能提早触发翻页	仅当下一块紧随其后时追加
文本行/图片不可拆	块整体搬页，留下难看的页尾空白	段落级"孤儿行"控制

还有一个藏在细节里的微妙之处：y += line_height * 0.5 中 0.5 是浮点、y 是 int，赋值时会截断取整——若行高为奇数，实际追加的半行会比"恰好一半"少 1px。这在视觉上无伤大雅，但它说明这段代码"够用但糙"：处处都是能跑就行的小妥协。改进的思路也不难，关键是把"是否处于块首行"纳入翻页条件——伪代码如下。

/* 改进示意：避免段落首行成为页面最后一行（防孤行） */
for (每行 i in textBlock->line_breaks) {
  bool is_first_line = (i == 0);
  if (is_first_line && y + line_height * 2 > page_height) {
    // 该块首行起算放不满两行 → 整块搬到下一页
    pages.push_back(new Page());
    y = 0;
  }
  /* ...原装填逻辑... */
}