Preface
Recently, to solve various tricky problems encountered during chapter
splitting, I had to dig deep into TxtEngine and debug many
implementation details. I had touched this engine before when solving
card-layout issues, but each time I only saw isolated pieces rather than
the whole picture.
To avoid being blocked by partial understanding, I decided to organize how this reading engine works from a more complete perspective, including file opening, layout, rendering, page turning, and related parts.
Opening a File
Getting File Size and File Stream
1 | // Given a file path, get the file size. |
Encoding Detection
Before parsing the file stream, we need to determine its encoding. So how do we identify the encoding of a file?
Identifying Files with a BOM
BOM stands for Byte Order Mark. It usually appears at the very beginning of a file and adds several extra invalid bytes to indicate the file’s encoding type. In some cases, the BOM also carries endian information. By reading the first few bytes of a file, we can determine how the file stream should be decoded.
Common UTF encodings include the following. UTF-16 and
UTF-32 also have big-endian and little-endian variants:
1 | FF FE 00 00 : UTF-32/UCS-4, little endian |
Why does UTF-8 not have an endian problem? Because when a character is represented in UTF-8, its Unicode code point is encoded into a byte array. When writing that byte array to memory, the bytes are simply written one by one in array order. There is no high-byte or low-byte issue. Therefore, the UTF-8 byte sequence for a Chinese character is the same on any kind of CPU.
On Microsoft Windows, UTF-8 files may include the BOM
EF BB BF, even though UTF-8 does not need it. This does not
mean UTF-8 needs byte order information; it only marks the file as
UTF-8. In some cases, this extra marker can cause trouble, so encoding
detection should account for it and avoid treating the BOM as part of
the file’s actual text.
At this point, when opening a file, if we see a BOM, we can identify whether the encoding is UTF-16, UTF-32, or UTF-8, and whether it is big endian or little endian.
Identifying Files Without a BOM
For files without a BOM, how should we determine their encoding?
Here, let us use UTF-8 and GBK as examples. GBK has no BOM. UTF-8 allows a BOM, but usually does not include one.
First, UTF-8:
UTF-8, or Unicode Transformation Format 8-bit, is a multibyte encoding designed for international text. It uses 8 bits, that is one byte, for English characters, and usually 24 bits, or three bytes, for Chinese characters. UTF-8 contains the characters needed by countries around the world, so it is an international encoding with strong universality. It is a multibyte character set. A Unicode character may be represented by one or more bytes, and the byte patterns follow clear rules:
1 | 1 byte: 0xxxxxxx |
By identifying the leading byte, we know how many bytes should be
parsed as one unit. The leading byte can only match one of these forms,
and every subsequent byte starts with 10. The pattern is
very obvious. So we can traverse the string according to these
characteristics to determine whether it is UTF-8 encoded.
Now GBK:
GBK is an extension of the national standard GB2312 and is backward
compatible with GB2312. GBK represents text using two bytes. Both
Chinese and English characters are represented with double bytes, and
the highest bit is set to 1 to distinguish Chinese. GBK encoding is
based on location codes and uses double-byte encoding for Chinese
characters and Chinese punctuation. The common encoding method is
0xA0 + area number, 0xA0 + position number.
For example, the Chinese character “安” has the decimal location code
1618, so its GBK encoding is 0xA0 + 16,
0xA0 + 18, which is 0xB0 0xB2. Although GBK
uses two-byte display, each byte also has a valid range. The overall GBK
range is 0x8140 to 0xFEFE; the first byte is
between 0x81 and 0xFE, and the second byte is
between 0x40 and 0xFE, excluding the
xx7F line.
From this, we can see that although GBK and UTF-8 files do not necessarily have markers, their encoded byte sequences have clear characteristics. We can usually identify whether a file is GBK or UTF-8 by examining the byte sequence.
However, this also introduces a certain performance cost. We have to check each character from beginning to end to determine whether it falls within the valid range of a given encoding. For example, the following code checks whether every character in the whole text conforms to UTF-8 rules:
1 | bool isUTF8( const char *str, int length ) |
After obtaining the file encoding, byte order, and related
information, we can determine some meaningless bytes such as
_docBOMSize.
Layout Settings
- Set the display area.
- Set the font type and font size.
- Set line height, line spacing, and paragraph spacing.
The display area, line spacing, and paragraph spacing are relatively straightforward. Here we mainly focus on font registration, line height, and character width.
Font Registration
If the font is built into the system, there is nothing special to do. But for non-system fonts, the font must first be loaded and registered:
1 | // Load font |
Character Width Calculation
The main character types involved in TxtEngine are ASCII
characters, CJK characters, and punctuation marks. For each font, under
a given line height, the corresponding character widths need to be
calculated.
- QQ Reader currently provides multiple font choices. Besides the built-in system Heiti font, it also provides many downloadable fonts such as Hanyi Shusong, Hanyi Qihei, Hanyi Kaiti, Founder Lanting, Founder Shusong, Founder Cartoon, Founder Qiti, and Founder Xinghei. Since font registration is supported, new fonts can continue to be added.
- For each font,
TxtEnginesupports font heights from 10 to 55.
1 |
- For each font and each line height, the corresponding character widths need to be calculated and cached separately. This is done lazily.
1 | unsigned char _bak_ascii_width[CacheFontSizeMax-CacheFontSizeMin+1][256][20]; // font size | ASCII character | font type |
ASCII Character Width
1 | // cache visible character width |
font_character_width determines whether the current font
type is a system font. If it is not, it also needs to locate the font
file, load it, and register it. Finally, it returns the corresponding
CTFontRef, and the character width is calculated from that
CTFontRef and the character.
1 | int font_string_width_byCTFont(CTFontRef ctFont, NSString* uniChar) |
Setting Chinese Character Width
CJK character width is basically fixed. Therefore, we only need to
calculate and cache the width of one representative character instead of
calculating every character’s width each time. This speeds up layout.
Here, the second parameter of font_character_width_2 uses
the first CJK Unicode code point, 0x4E00, to represent the
width of all CJK symbols.
1 | (chr >= 0x4E00 && chr <= 0x9FBF) // 4E00-9FBF: CJK Unified Ideographs |
1 | // cache chinese character |
Setting Punctuation Width
The punctuation marks used during layout, here mainly full-width punctuation because half-width punctuation should be included in ASCII, include the following:
1 | // Punctuation types |
For these punctuation marks, the engine calculates and caches each punctuation mark’s width under a certain font size. The calculation process is the same as the ASCII width calculation above.
1 | // cache biaodian character |
Layout
After opening a file, the engine usually enters from an anchor. An anchor contains two parts: paragraph offset and line offset.
Paragraph Splitting
If the paragraph linked list for the anchor has not been built yet,
paragraph parsing is triggered. Paragraph splitting is based on these
separators: \n\r, \n, \r, and
\r\n. Each time, the engine searches the current data
stream for the next separator. Once one is found, the start offset and
size of a new paragraph can be determined from the offsets before and
after it.
1 | - (BOOL) NextBreaker:(unsigned char *) buffcountCharInWidth |
Take UTF-8 as an example:
1 | "第1章 下辈子也不会爱上你\r\n6月6日,星期六。\r\n 这是一个十分吉利的日子,更是一个黄道吉日。\r\n 这一日,是京城有名的富家之女梁贝璇与其男友曹瑞年的婚礼,婚礼早就被各路媒体公布出去了,好多人的眼睛都在看着这一个家室及其不匹配的婚姻,所有人都报以怀疑的态度,只是没有人会主动说出来。\r\n 此时的梁贝璇坐在宽敞明亮、奢华至极的房间内,穿着洁白定制的婚纱,脸上带着甜蜜的梦幻般的笑容。\r\n 只是这样的笑容在她收到一个快递之后就彻底的失去了......\r\n |
This is part of a chapter. How do we split it into paragraphs?
Naturally, by traversing from front to back and looking for
\r\n until the end.
1 | bool qr_utf8_next_breaker( unsigned char * buff, unsigned long buff_size, unsigned long * brk_off, unsigned long * skip_bytes ) |
After one traversal, we can find the start and end offsets of a paragraph.
Getting Character Count in a Paragraph
After obtaining the byte stream corresponding to a paragraph, we need to determine how many characters it contains.
1 | - (BOOL) CharCount:( unsigned char * )buff |
Still using UTF-8 as an example, in common cases each UTF-8 character may use one to three bytes:
1 | 1 byte: 0xxxxxxx 0000-0111, eight cases, all one byte |
With this foundation, we can use an array named __bpc to
store byte counts. Take the high four bits of the first UTF-8 byte,
convert it into an index, and directly obtain the corresponding byte
count.
1 | static const unsigned long __bpc[16] = |
Then we can quickly calculate the number of characters represented by a section of byte stream.
1 | unsigned long qr_utf8_charcnt( unsigned char * buff, unsigned long buff_size ) |
Generating Paragraph Structures
TxtEngine has two paragraph structures: paragraph text,
__struct_TextPrgf_Text, and paragraph attributes,
__struct_TextPrgf.
1 | typedef struct __struct_TextPrgf_Text TextPrgf_Text_t; |
1 | typedef struct __struct_TextPrgf TextPrgf_t; |
One thing worth noting is that the first field of the paragraph text
structure, link, is exactly the paragraph attribute type.
So given a paragraph text structure:
1 | __struct_TextPrgf_Text textPrgf_Text; |
It can be directly cast:
1 | __struct_TextPrgf textPrgf = (__struct_TextPrgf)textPrgf_Text; |
Earlier, we parsed the paragraph’s start and end offsets, calculated its character count, and determined the amount of memory to allocate. Now we can create the paragraph:
1 | // Allocate space |
1 | TextPrgf_ptr_t qr_alloc_prgf_text( unsigned long char_cnt ) |
Calculating Character Offsets
This step calculates the byte offset of each character relative to the file.
1 | [_endcoder countCharactersOffset:&_readCache[prgf_offset] |
1 | - (BOOL)_utf8CountCharactersOffset:(unsigned char *)buff |
Encoding Conversion
Convert the character encoding to Unicode and store it in
&text_prgf->wide_buff[0].
1 | - (BOOL) EncodeUCS2:( unsigned short *) dst_buff |
Here is an example that converts UTF-8 to Unicode:
1 | unsigned long qr_utf8_to_ucs2( unsigned short * buff, unsigned long buff_size, unsigned char * utf8_str, unsigned long utf8_len,unsigned long* used_utf8_len ) |
Determining Paragraph Type
To determine the concrete type of a paragraph, the engine needs to identify paragraph categories.
- Determine whether a paragraph is the title of a chapter.
1 | - (BOOL)isPrafChapterTitle:( TextPrgf_Text_ptr_t) text_prgf group:(TextPrgfGroup_ptr_t)groupPtr |
- Determine whether the paragraph is an author’s note. An author’s note may contain multiple paragraphs, and each paragraph ends with the special string
"\u3000\u2029\u3000". The first paragraph of an author’s note starts with"\u2029\u3000\u2029".
1 | // Whether this is an author's note |
- Determine whether the paragraph is
"(本章完)". This checks whether the content pointed to byptris"(本章完)\r\n".
1 | - (BOOL)isParagraphEndStr:(unsigned char *)ptr |
Paragraph Line Breaking
For paragraph splitting, encoding conversion, and character-offset calculation, the work only needs to be done once. It does not need to be updated later because this information is relatively independent and does not depend on other layout conditions.
However, laying out paragraph text according to the current font, direction, and other settings does depend on layout-related settings, such as drawing area size, orientation, font size, font color, line spacing, and paragraph spacing. Once any of these settings changes, the layout here also needs to be updated.
The essence of layout is: according to the layout settings, generate line-by-line layout results from one paragraph. Note that height-offset information is not included here.
1 | // This code omits the logic for detecting chapter titles. |
First, why is mid_off introduced here?
The main reason is that some paragraphs may cross page boundaries. In
that case, if a rotation occurs, the current page continues to lay out
from the starting anchor again. The last line of the paragraph that
crossed into the previous page may not fill a full line. Therefore, this
rule is introduced: for a paragraph crossing into the previous page, the
last line is only laid out up to the character before the anchor. This
means the last line of the previous page may break differently. For
paragraphs that do not cross pages, mid_off is naturally 0,
so the first half of the logic does not run.
The core of line breaking is calculating the width of each character and deciding, based on the page width, whether a given character is the last character of the current line. This produces one line inside the paragraph.
In addition to the normal calculation process, there are extra rules:
- Filter out emoji characters.
- Punctuation rules for avoiding punctuation at line heads and tails:
- If the current line ends with a left quote, left parenthesis, left book-title mark, left single quote, em dash, or ellipsis, move it to the next line.
- If the next line starts with two consecutive punctuation marks and the current line does not end with punctuation, move the last character of the current line to the next line to avoid punctuation appearing at the start of a line.
- If the next line starts with only one punctuation mark, move that punctuation mark up to the previous line.
- A comma or period at the end of a line counts as half width.
- After each line is laid out, spaces need to be considered and
character
xpositions and widths are recalculated.
1 | - (unsigned long)countCharInWidth:(unsigned short*)buff |
English text has additional layout rules. Sometimes an English word or number is too long, and the last word or number of a line has not finished when the line reaches the edge. To avoid breaking a word or number across lines, the engine follows these rules:
- If the first character of the next line is not an English letter or number, the current line can fully contain the last word. This is normal, so return directly.
- If the first character of the next line is a number or English letter, check whether the last character of the current line is also a letter or number.
- If it is, count the length of the last word or number on the current line. If the word or number length is limited, move the front part of that word or number to the next line. Otherwise, do nothing.
- If it is not, do nothing.
1 | unsigned long qr_relayout_english_2(unsigned short * buff, |
Inserted Paragraph Handling
The business layer may insert data into the layout.
- Some content needs to be inserted into the middle of a paragraph, such as “brilliant ideas”. Some needs to be inserted at the end of a paragraph, such as various business data at the end of a chapter: text ads, image ads, Q&A, cards, Guangdiantong data, and so on.
- Some inserted paragraphs need to be laid out like normal text, such as author’s notes. Their layout rules are the same as body text, except that the font, font size, and color may differ. Others only need placeholders. The placeholder size is decided by the business layer. After layout is complete, the engine needs to pass the placeholder coordinates back to the business layer, and the business layer completes its own logic within the reserved area.
1 | TextPrgf_ptr_t custom_prgf = qr_alloc_prgf_space(); |
The insertion logic is as follows:
1 | - (void)_insertPrgf:(TextPrgf_ptr_t)dstPrgf |
Rendering
With all the preparation from the layout process, rendering becomes relatively simple:
- Prepare the canvas, pen, and color.
- Find the current page’s starting paragraph pointer and starting line pointer.
- Determine line height, line spacing, and paragraph spacing.
The engine then draws characters line by line according to the
x and w values calculated during layout, until
the current canvas can no longer contain more content.
Some code is omitted here to make the overall flow easier to follow:
1 | - (BOOL)repaint:(QRCanvas *)canvas rect:(QRRect *)rect |
The final real drawing still uses the system method:
1 | [text drawAtPoint:CGPointMake(x, y) withAttributes:@{NSFontAttributeName : gc->fontBatch, NSForegroundColorAttributeName : textColor}]; |
There are a few extra details worth noting:
- Highlight areas need to be drawn, such as note underlines. So after each line is drawn, a check must be performed.
- At the end of each text paragraph, the engine checks whether a paragraph-comment bubble needs to be drawn.
- When customized business content appears in the middle, the engine reserves space according to the given height.
Page Turning
After the current page has been rendered, moving to the next or
previous page requires finding the starting anchor of that page.
TxtEngine mainly uses these methods:
1 | - (BOOL)moveNextPage; |
The logic of the first two methods is roughly the same as the rendering method. The difference is that they only calculate the Y offset and do not actually draw.
moveNextPage: starting from the current page anchor, lay out line by line to the end of the current page, then find the starting paragraph offset and line offset of the next page.movePrevPage: starting from the current page anchor, lay out backwards to the beginning of the previous page, then find the starting paragraph offset and line offset of the previous page.
There are several flaws here:
- Since the current page has already been rendered, finding the starting anchor of the next page should be quick using the current page’s tail pointer. There is no need to run a large loop again. Unfortunately, although
TxtPagewas introduced long ago and already contains the tail pointer, it was not used. This is what Siyu is currently working on.- Determining whether the current page is the end of the chapter,
isBottom, should also only require checking the tail pointer. Unfortunately,isBottomalso runs a large loop.- None of these methods caches anything after finishing the loop, causing the large loop to run many times.
- The two loops above and the rendering loop have certain differences, which sometimes leads to missing paragraphs or repeated layout.
If TxtPage can record the current page’s start pointer
and end pointer, then each page’s layout and rendering process only
needs to run once. This removes a lot of unnecessary performance cost,
ensures that rendering and layout results are consistent, and avoids
many annoying layout issues.
1 | @interface TxtPage : NSObject |
Paragraph Cache
When turning pages forward and backward, the engine often first needs to determine whether the paragraphs already built in memory are sufficient to construct the previous or next page.
- In some cases, the chapter file is large and cannot be read entirely at once.
- In some cases, the reader enters from an anchor in the middle of a chapter. At that point, only the data stream after the current anchor is loaded. When turning to the previous page, the engine needs to load the data stream before the anchor and build the previous paragraphs.
The threshold used here is cache_bytes = 8 * 1024.
1 | /** |
1 | /** |
The newly loaded cache is immediately parsed into a paragraph linked
list, including paragraph splitting, encoding conversion,
character-offset calculation, and line layout according to the current
font, direction, and other conditions. Finally, the newly parsed
prgf_group is merged into the global paragraph group
_prgfGroup.
1 | qr_merge_front_prgf( &_prgfGroup, &prgf_group ); |
Online-book chapter files are usually small, so in most cases the paragraph linked list for a chapter can be cached in memory. But when the file is large, such as an imported book, the paragraph linked list cannot always stay in memory. The engine needs to cache paragraphs within a certain distance before and after the current reading offset, and paragraphs outside that range need to be cleared.
For the concrete logic, see:
1 | - (void) recycleFromTop:(unsigned long) recycle_size; |
General Idea
For online books, chapter files are generally small, so we can try a new approach:
Read the entire chapter file at once, split paragraphs, convert encoding, break lines, paginate from beginning to end according to the current settings, and cache the pagination results. During rendering, use the page number to directly obtain the page’s start and end pointers and draw from them. This removes the difference between forward and backward page turning, and avoids missing paragraphs or repeated layout.
Chapter Splitting
What is chapter splitting? Some files may contain multiple chapters, and apart from the file itself there may be no other information. In that case, chapter information has to be determined from the file content, including the number of chapters, each chapter title, content, and starting offset.
This process is essentially searching for patterns like
"第xxx章(章节回卷篇部)". The process of searching for
these characters is very similar to searching for \n\r
earlier.
1 | static const unsigned short __charset_spc[] = |
Summary
This article still has many shortcomings and will be improved later.