How the TXT Engine Works

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
2
3
4
5
6
7
// Given a file path, get the file size.
_fileSize = [[[NSFileManager defaultManager] attributesOfItemAtPath:filePath error:nil] fileSize];

// Get the file stream. If the file is large, it needs to be read in batches.
unsigned long readSize = (_fileSize < QR_MAX_GUESS_LEN ? _fileSize:QR_MAX_GUESS_LEN);
NSData* data = [_fileHandle readDataOfLength:readSize];
unsigned char* buff = (unsigned char*)[data bytes];

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
2
3
4
5
FF FE 00 00 : UTF-32/UCS-4, little endian
00 00 FE FF : UTF-32/UCS-4, big endian
FF FE : UTF-16, little endian
FE FF : UTF-16, big endian
EF BB BF : UTF-8, no endian distinction

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
2
3
4
5
6
1 byte:  0xxxxxxx
2 bytes: 110xxxxx 10xxxxxx
3 bytes: 1110xxxx 10xxxxxx 10xxxxxx
4 bytes: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
5 bytes: 111110xx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
6 bytes: 1111110x 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

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
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
bool isUTF8( const char *str, int length )
{
int i, mode = 0, m2;
unsigned long ucs;
char ch;

for( i = 0 ; i < length - 2 ; i++ ){
ch = str[ i ];
if( mode == 0 )
{
if( (ch&0x80) == 0 ) continue;
if( (ch&0xe0) == 0xc0 ){ mode = m2 = 1; ucs = (ch&0x1f); continue; }
if( (ch&0xf0) == 0xe0 ){ mode = m2 = 2; ucs = (ch&0x0f); continue; }
if( (ch&0xf8) == 0xf0 ){ mode = m2 = 3; ucs = (ch&0x07); continue; }
if( (ch&0xfc) == 0xf8 ){ mode = m2 = 4; ucs = (ch&0x03); continue; }
if( (ch&0xfe) == 0xfc ){ mode = m2 = 5; ucs = (ch&0x01); continue; }
return false;
}
else
{
if( (ch&0xc0) != 0x80 ) return 0;
ucs <<= 6; ucs += (ch&0x3f);
mode--;
if( !mode ){
if( m2 == 1 && ucs < 0x0000080 ) return 0;
if( m2 == 2 && ucs < 0x0000800 ) return 0;
if( m2 == 3 && ucs < 0x0010000 ) return 0;
if( m2 == 4 && ucs < 0x0200000 ) return 0;
if( m2 == 5 && ucs < 0x4000000 ) return 0;
}
}
}
return true;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
// Load font
NSString *fontFilePath = [self getFontFilePath:fontType];
NSString *url = [NSURL fileURLWithPath:fontFilePath];
CGDataProviderRef fontDataProvider = CGDataProviderCreateWithURL((CFURLRef)url);
CGFontRef newFont = CGFontCreateWithDataProvider(fontDataProvider);
CGDataProviderRelease(fontDataProvider);

// Register font
CTFontManagerRegisterGraphicsFont(newFont, NULL);

// Get CTFontRef
CTFontRef ctFont = CTFontCreateWithGraphicsFont(newFont, fontSize,NULL,NULL);
return ctFont;

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, TxtEngine supports font heights from 10 to 55.
1
2
#define CacheFontSizeMin               10  
#define CacheFontSizeMax 55
  • For each font and each line height, the corresponding character widths need to be calculated and cached separately. This is done lazily.
1
2
3
unsigned char       _bak_ascii_width[CacheFontSizeMax-CacheFontSizeMin+1][256][20];     // font size | ASCII character | font type
unsigned char _bak_wchar_width[CacheFontSizeMax-CacheFontSizeMin+1][20]; // font size | font type
unsigned char _bak_biaodian_width[CacheFontSizeMax-CacheFontSizeMin+1][18][20]; // font size | punctuation character | font type

ASCII Character Width

1
2
3
4
5
6
7
8
// cache visible character width
for ( i = 0; i < 256; ++i )
{
if ( _bak_ascii_width[nFontSize - CacheFontSizeMin][i][nFontType] == 0xff )
{
_bak_ascii_width[ nFontSize - CacheFontSizeMin][i][nFontType] = font_character_width([_setting parseFont], (QWCHAR)(i));
}
}

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
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
int font_string_width_byCTFont(CTFontRef ctFont, NSString* uniChar)
{
UniChar *characters;
CGGlyph *glyphs;
CFIndex count = [uniChar length] ;//1;

// Allocate our buffers for characters and glyphs.
characters = (UniChar *)malloc(sizeof(UniChar) * count);
//assert(characters != NULL);

glyphs = (CGGlyph *)malloc(sizeof(CGGlyph) * count);
//assert(glyphs != NULL);

// Get the characters from the string.
CFStringGetCharacters((CFStringRef)uniChar, CFRangeMake(0, count), characters);

// Get the glyphs for the characters.
CTFontGetGlyphsForCharacters(ctFont, characters, glyphs, count);

// Do something with the glyphs here, if a character is unmapped
CGSize *cSize = (CGSize *)malloc(sizeof(CGSize)*count);

// English fonts may have fractional widths, so round here to avoid squeezing English text.
int fontwidth = (int) (0.5 + CTFontGetAdvancesForGlyphs(ctFont, kCTFontDefaultOrientation, glyphs, cSize, count) );

// Free our buffers
free(characters);
free(glyphs);
free(cSize);

return fontwidth;

}

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
2
3
4
5
6
7
8
9
10
(chr >= 0x4E00 && chr <= 0x9FBF)            // 4E00-9FBF: CJK Unified Ideographs
(chr >= 0xF900 && chr <= 0xFAFF) // F900-FAFF: CJK Compatibility Ideographs
(chr >= 0xFE30 && chr <= 0xFE4F) // FE30-FE4F: CJK Compatibility Forms
(chr >= 0xFF00 && chr <= 0xFFEF) // FF00-FFEF: Halfwidth and Fullwidth Forms, full-width punctuation and full-width ASCII
(chr >= 0x3200 && chr <= 0x32FF) // 3200-32FF: Enclosed CJK Letters and Months
(chr >= 0xAC00 && chr <= 0xD7AF) // Hangul syllables
(chr >= 0x1100 && chr <= 0x11FF) // Hangul Jamo
(chr >= 0x3130 && chr <= 0x318F) // Hangul Compatibility Jamo
(chr >= 0x3040 && chr <= 0x309F) // Hiragana
(chr >= 0x30A0 && chr <= 0x30FF) // Katakana
1
2
3
4
5
6
// cache chinese character
int nChineseWidth = font_character_width_2([_setting parseFont], (QWCHAR)0x4E00 , nFontType);
if ( _bak_wchar_width[nFontSize - CacheFontSizeMin][nFontType] == 0xff )
{
_bak_wchar_width[nFontSize - CacheFontSizeMin][nFontType] = nChineseWidth;
}

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
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
// Punctuation types
static unsigned short biaodian_array[] =
{
U_PUNCT_COMMA, // 0xFF0C | ,
U_PUNCT_FULLPOINT, // 0x3002 | 。
U_PUNCT_QUESTION, // 0xFF1F | ?
U_PUNCT_SEMICOLON, // 0xFF1B | ;
U_PUNCT_EXCLAMATION, // 0xFF01 | !
U_PUNCT_COLON, // 0xFF1A | :
U_PUNCT_PAUSE, // 0x3001 | 、
U_PUNCT_LEFTSINGLEQUOTE, // 0x2018 | ‘
U_PUNCT_RIGHTSINGLEQUOTE, // 0x2019 | ’
U_PUNCT_LEFTDOUBLEQUOTE, // 0x201C | “
U_PUNCT_RIGHTDOUBLEQUOTE, // 0x201D | ”
U_PUNCT_LEFTBOOKQUOTE, // 0x300A |《
U_PUNCT_RIGHTBOOKQUOTE, // 0x300B | 》
U_PUNCT_LEFTBRACKET, // 0xFF08 |(
U_PUNCT_RIGHTBRACKET, // 0xFF09 | )
U_PUNCT_CONNECT, // 0x002D | -
U_PUNCT_PERCENT, // 0x0025 | %
U_PUNCT_SPACER, // 0x00B7 | .
U_PUNCT_POZHE, // 0x2014 | em dash
U_PUNCT_SHENGLUE, // 0x2026 | ellipsis
U_PUNCT_LEFTANCIENTEQUOTE, // 0x300C | old-style left quote 「
U_PUNCT_RIGHTANCIENTEQUOTE // 0x300D | old-style right quote 」
};

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
2
3
4
5
6
7
8
9
// cache biaodian character
int nLen = sizeof( biaodian_array ) / sizeof ( unsigned short) ;
for ( i = 0; i < nLen; ++i )
{
if ( _bak_biaodian_width[ nFontSize - CacheFontSizeMin][i][nFontType] == 0xff )
{
_bak_biaodian_width[ nFontSize - CacheFontSizeMin][i][nFontType] = font_character_width_2([_setting parseFont], (QWCHAR)(biaodian_array[i]) , nFontType);
}
}

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
2
3
4
5
- (BOOL) NextBreaker:(unsigned char *) buffcountCharInWidth
buffSize:(unsigned long) buff_size
buffOff:(unsigned long )buff_off
brkOff:(unsigned long * )brk_off
skipBytes:(unsigned long * )skip_bytes

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
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
bool qr_utf8_next_breaker( unsigned char * buff, unsigned long buff_size, unsigned long * brk_off, unsigned long * skip_bytes )
{
bool found = false;
unsigned long offset;

for ( offset = 0; offset < buff_size; ++offset )
{
// If we have reached the end of the binary stream, break.
// End condition: buff[offset] == 0x00
if ( qr_is_end_char( buff[offset] ) )
break;

// If \r is found, there are two cases: \r\n and \r
if ( 0x0D == buff[offset] ) // \r
{
*brk_off = offset;

if ( (offset + 1 < buff_size) && (0x0A == buff[offset + 1]) )
{
*skip_bytes = offset + 2; // \r\n
}
else
{
*skip_bytes = offset + 1; // \r
}

found = true;
break;
}
// If \n is found, there are two cases: \n\r and \n
else if ( 0x0A == buff[offset] ) // \n
{
*brk_off = offset;

if ( (offset + 1 < buff_size) && (0x0D == buff[offset + 1]) )
{
*skip_bytes = offset + 2; // \n\r
}
else
{
*skip_bytes = offset + 1; // \n
}

found = true;
break;
}
}

// Boundary check
if (offset >= buff_size)
{
found = false;
*skip_bytes = buff_size;
}

return found;
}

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
2
3
- (BOOL)    CharCount:( unsigned char * )buff
buffSize:(unsigned long) buff_size
charCount:(unsigned long * )cnt

Still using UTF-8 as an example, in common cases each UTF-8 character may use one to three bytes:

1
2
3
4
1 byte:  0xxxxxxx  0000-0111, eight cases, all one byte
2 bytes: 110xxxxx 1100 and 1101, indexes 12 and 13, both two bytes
3 bytes: 1110xxxx 1110, one case, three bytes
0 bytes: all other cases are zero bytes

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
2
3
4
5
6
7
8
9
static const unsigned long __bpc[16] =
{
1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 2, 3, 0
};

int qr_utf_char_bytes(unsigned char ch)
{
return (int)(__bpc[ch >> 4]);
}

Then we can quickly calculate the number of characters represented by a section of byte stream.

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
unsigned long   qr_utf8_charcnt( unsigned char * buff, unsigned long buff_size )
{
unsigned long chr_cnt;
unsigned long offset;
unsigned long chr_bytes;

if ( NULL == buff || 0 == buff_size )
return 0;

for ( chr_cnt = 0, offset = 0; offset < buff_size; ++chr_cnt )
{
if ( qr_is_end_char( buff[offset] ) )
break;

chr_bytes = qr_utf_char_bytes( buff[offset] );//
if ( chr_bytes == 0 )
break;

if ( offset + chr_bytes > buff_size )
break;

offset += chr_bytes;
}

return chr_cnt;
}

Generating Paragraph Structures

TxtEngine has two paragraph structures: paragraph text, __struct_TextPrgf_Text, and paragraph attributes, __struct_TextPrgf.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct __struct_TextPrgf_Text        TextPrgf_Text_t;
typedef struct __struct_TextPrgf_Text * TextPrgf_Text_ptr_t;

// Paragraph text data structure
struct __struct_TextPrgf_Text
{
TextPrgf_t link; // Paragraph attributes
unsigned long line_count;
TextLine_ptr_t first_line; // [strong ref]
TextLine_ptr_t last_line; // [strong ref]

unsigned short *wide_buff; // Paragraph text buffer (UCS2 encoding)
unsigned long wide_size; // Size of paragraph text buffer
QRRect *char_rects; // character drawrect array
unsigned long *charactersOffsets; // Byte offset of each character in the paragraph relative to the file start
long charactersCountAddOne; // Number of characters in the paragraph plus one
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct __struct_TextPrgf            TextPrgf_t;
typedef struct __struct_TextPrgf * TextPrgf_ptr_t;

// Paragraph attribute data structure
struct __struct_TextPrgf
{
TextPrgf_ptr_t prev; // [weak ref]
TextPrgf_ptr_t next; // [weak ref]

unsigned long type; // QR_TEXT_PRGF_TYPE_XXX
unsigned long attrib; // QR_TEXT_PRGF_ATTR_XXX
unsigned long offset; // Offset in current charpter //..file
unsigned long size; // Paragraph size in charpter //file

unsigned long page_index;
unsigned long charpter_index;
// Index of chapter-tail page model
int tail_index;
int need_remove_para_space;//0 means no, 1 means yes
};

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
2
3
4
// Allocate space
last_prgf = qr_alloc_prgf_text( chr_count+2 );//add two space ericni
last_prgf->need_remove_para_space = 0;
last_prgf->tail_index = -1;
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
TextPrgf_ptr_t qr_alloc_prgf_text( unsigned long char_cnt )
{
TextPrgf_Text_ptr_t prgf = NULL;

if ( 0 == char_cnt ) return NULL;

prgf = malloc(sizeof(TextPrgf_Text_t));

long charactersCountAddOne = char_cnt + 1;

prgf->link.prev = NULL;
prgf->link.next = NULL;
prgf->link.type = QR_TEXT_PRGF_TYPE_TEXT;
prgf->link.attrib = 0;
prgf->link.offset = 0;
prgf->link.size = 0;

prgf->wide_buff = NULL;
prgf->char_rects = NULL;
prgf->wide_size = QR_ROUND_UP_4( (charactersCountAddOne << 1) );

prgf->line_count = 0;
prgf->first_line = NULL;
prgf->last_line = NULL;

prgf->wide_buff = malloc(prgf->wide_size);

// alloc memory for char_rects
prgf->char_rects = malloc(charactersCountAddOne * sizeof(QRRect));
memset(prgf->char_rects, 0, charactersCountAddOne * sizeof(QRRect));

prgf->charactersOffsets = malloc(charactersCountAddOne * sizeof(unsigned long));
memset(prgf->charactersOffsets, 0, charactersCountAddOne * sizeof(unsigned long));

prgf->charactersCountAddOne = charactersCountAddOne;

return (TextPrgf_ptr_t)prgf;
}

Calculating Character Offsets

This step calculates the byte offset of each character relative to the file.

1
2
3
4
5
[_endcoder countCharactersOffset:&_readCache[prgf_offset]
characters:chr_count
buffSize:prgf_size
baseOffset:file_offset + prgf_offset
characterOffsets:text_prgf->charactersOffsets];
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
- (BOOL)_utf8CountCharactersOffset:(unsigned char *)buff
characters:(unsigned long)characters
buffSize:(unsigned long)buffSize
baseOffset:(unsigned long)baseOffset
offsets:(unsigned long *)offsets
{
if (NULL == buff || 0 == buffSize || offsets == NULL) {
return NO;
}

unsigned long characterOffset = baseOffset;

// characterIndex < characters prevents offsets from going out of bounds.
for (unsigned long characterIndex = 0, offset = 0;offset < buffSize && characterIndex < characters;++characterIndex) {

if (qr_is_end_char(buff[offset])) {
break;
}

*(offsets + characterIndex) = characterOffset;

// Each UTF-8 character may take one to three bytes.
//
unsigned long characterBytes = qr_utf_char_bytes(buff[offset]);

if (characterBytes == 0) {
break;
}

if (offset + characterBytes > buffSize) {
break;
}

offset += characterBytes;

// Offset of the next character.
//
characterOffset += characterBytes;
}

return YES;
}

Encoding Conversion

Convert the character encoding to Unicode and store it in &text_prgf->wide_buff[0].

1
2
3
4
5
6
- (BOOL)    EncodeUCS2:( unsigned short *) dst_buff
destSize:(unsigned long )dst_size
srcBuff:(unsigned char *) src_buff
srcSize:(unsigned long) src_size
convLen:(unsigned long * )conv_len
usedBytes:(unsigned long * )used_bytes

Here is an example that converts UTF-8 to Unicode:

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
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 )
{
unsigned long conv_len = 0;
unsigned long char_cnt = 0;
unsigned long char_bytes;
unsigned char * us_utf8_str = (unsigned char*)utf8_str;
unsigned long i;
unsigned short tmp_ch = '\0';

if ( NULL == buff || NULL == us_utf8_str || buff_size < 2 || 0 == utf8_len )
return 0;

*used_utf8_len = 0;

if ( utf8_len >= 3 && (us_utf8_str[0] == 0xEF && us_utf8_str[1] == 0xBB && us_utf8_str[2] == 0xBF) )
{
// skip BOM
us_utf8_str += 3;
*used_utf8_len += 3;
}

for ( i = 0; i < utf8_len; ++i )
{
if ( '\0' == *us_utf8_str ) break;

char_bytes = __utf8_bpc[((unsigned char)*us_utf8_str) >> 4];


if ( 1 == char_bytes )
{
tmp_ch = (unsigned short)us_utf8_str[0];
*used_utf8_len += char_bytes;
}
else if ( 2 == char_bytes )
{
if ( '\0' != us_utf8_str[1] )
{
tmp_ch = ((unsigned short)(us_utf8_str[0] & 0x1F) << 6) | ((unsigned short)(us_utf8_str[1] ^ 0x80));
*used_utf8_len += char_bytes;
}
}
else if ( 3 == char_bytes )
{
if ( '\0' != us_utf8_str[1] && '\0' != us_utf8_str[2] )
{
tmp_ch = ((unsigned short)(us_utf8_str[0] & 0x0F) << 12) | ((unsigned short)(us_utf8_str[1] ^ 0x80) << 6) | ((unsigned short)(us_utf8_str[2] ^ 0x80));
*used_utf8_len += char_bytes;
}
}
else
{
*used_utf8_len += 1;
}

if ( char_cnt >= ((buff_size / 2) - 1) )
break;

buff[char_cnt] = tmp_ch;
char_cnt += 1;


conv_len += 2;
us_utf8_str += char_bytes;
}

buff[char_cnt] = '\0';

return conv_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
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
- (BOOL)isPrafChapterTitle:( TextPrgf_Text_ptr_t) text_prgf group:(TextPrgfGroup_ptr_t)groupPtr
{
if (_isLocal || groupPtr == NULL) {
return NO;
}

BOOL isTitle = NO;
if (groupPtr->head == NULL && groupPtr->tail == NULL && text_prgf->link.offset == 0 && _offset <= 4) {
// Used to determine whether it is a title when jumping from the table of contents
// or opening from the bookshelf and the group is still an empty linked list.
isTitle = YES;
}
else if (_offset <= 4 || groupPtr->head != NULL)
{
// User relayout. At this point the group already has a linked list.
if (( TextPrgf_Text_ptr_t)groupPtr ->head == text_prgf && text_prgf->link.offset == 0) {
isTitle = YES;
}
}
else if (_offset > 4)
{
// The user read from the middle of a chapter, returned to the bookshelf,
// and then entered the reading page again.
if (groupPtr->head == NULL && groupPtr->tail == NULL && text_prgf->link.offset == 0) {
isTitle = YES;
}
}
return isTitle;
}
  • 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
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
// Whether this is an author's note
- (BOOL)isAuthorTipsWithParagraphFirstPtr:(unsigned char *)firstPtr endPtr:(unsigned char *)endPtr
{
if (strlen((const char *)endPtr) < QRAuthorTipsBeforeEndMarkLength || _isLocal)
{
return NO;
}

// Author's note ends with special characters "\u3000\u2029\u3000"
return (endPtr[0] == 0xe3 && endPtr[1] == 0x80 && endPtr[2] == 0x80 &&
endPtr[3] == 0xe2 && endPtr[4] == 0x80 && endPtr[5] == 0xa9 &&
endPtr[6] == 0xe3 && endPtr[7] == 0x80 && endPtr[8] ==0x80);
}

// Whether this is the first paragraph of an author's note
- (BOOL)isFirstParagOfAuthorTipsWithFirstPtr:(unsigned char *)firstPtr
{
if (strlen((const char *)firstPtr) < QRAuthorTipsBeforeEndMarkLength || _isLocal)
{
return NO;
}

// The first paragraph of an author's note starts with "\u2029\u3000\u2029"
return (firstPtr[0] == 0xe2 && firstPtr[1] == 0x80 && firstPtr[2] == 0xa9 &&
firstPtr[3] == 0xe3 && firstPtr[4] == 0x80 && firstPtr[5] == 0x80 &&
firstPtr[6] == 0xe2 && firstPtr[7] == 0x80 && firstPtr[8] == 0xa9);
}
  • Determine whether the paragraph is "(本章完)". This checks whether the content pointed to by ptr is "(本章完)\r\n".
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
- (BOOL)isParagraphEndStr:(unsigned char *)ptr
{
if (!ptr || _isLocal || strlen((const char *)ptr) != 13) {
return NO;
}

// Determine whether the content pointed to by ptr is "(本章完)\r\n"
//
return *ptr == '(' &&
*(ptr + 1) == 0xe6 && *(ptr + 2) == 0x9c && *(ptr + 3) == 0xac && // "本" utf8
*(ptr + 4) == 0xe7 && *(ptr + 5) == 0xab && *(ptr + 6) == 0xa0 && // "章" utf8
*(ptr + 7) == 0xe5 && *(ptr + 8) == 0xae && *(ptr + 9) == 0x8c && // "完" utf8
*(ptr + 10) == ')' &&
*(ptr + 11) == '\r' &&
*(ptr + 12) == '\n';
}

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
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
// This code omits the logic for detecting chapter titles.
- (BOOL)relayoutTextPrgf:(TextPrgf_Text_ptr_t) text_prgf midOff:(unsigned long) mid_off group:(TextPrgfGroup_ptr_t)groupPtr

{
//TODO: Layout one paragraph
unsigned long ret_val;
unsigned long width;
unsigned long length;
unsigned long bound_w;

unsigned long index;
unsigned long max_len;
unsigned long offset;
TextLine_ptr_t text_line;
QRFont* doc_font;
QRFont* doc_title_font = _titleSetting.font_obj ;

if ( NULL != text_prgf->last_line )
{
offset = text_prgf->last_line->offset;
if ( offset + text_prgf->last_line->length >= text_prgf->wide_size )
return NO;
}

doc_font = _setting.font_obj;
if (QR_TEXT_PRGF_TYPE_AUTHOR == text_prgf->link.type ||
QR_TEXT_PRGF_TYPE_BUSINISS_TEXT == text_prgf->link.type) {
doc_font = [self authorTipsSetting].font_obj;
}

max_len = text_prgf->wide_size / 2;
bound_w = _docBoundRc.w;

index = 0;

// First perform line breaking for characters from 0 to mid_off.
if ( mid_off > 0 )
{
for ( offset = 0; offset < mid_off; offset += length, ++index )
{
ret_val = [doc_font countCharInWidth:&text_prgf->wide_buff[offset] rect:&text_prgf->char_rects[offset] length:(mid_off - offset) maxWidth:bound_w outWidth:&width count:&length alignmeng:0];

if ( QR_OK != ret_val || 0 == length ) break;

// 20151023 lucas: English and number line breaking should not split words.
qr_relayout_english_2(&text_prgf->wide_buff[offset] , mid_off - offset , 0, &length);

text_line = qr_alloc_line();
if ( NULL == text_line ) break;

text_line->index = index;
text_line->offset = offset;
text_line->width = width;
text_line->length = length;
text_line->isCharpterTitle = 0;
qr_push_back_line( text_prgf, text_line );
}
}

// Then perform line breaking from mid_off to the end.
for ( offset = mid_off; offset < max_len; offset += length, ++index )
{
ret_val = [doc_font countCharInWidth:&text_prgf->wide_buff[offset] rect:&text_prgf->char_rects[offset] length:(max_len - offset) maxWidth:bound_w outWidth:&width count:&length alignmeng:0];

if ( QR_OK != ret_val || 0 == length ) break;

// 20151023 lucas: English and number line breaking should not split words.
qr_relayout_english_2(&text_prgf->wide_buff[offset] , max_len - offset , 0, &length);

text_line = qr_alloc_line();
if ( NULL == text_line ) break;

text_line->index = index;
text_line->offset = offset;
text_line->width = width;
text_line->length = length;

text_line->isCharpterTitle = 0;
qr_push_back_line( text_prgf, text_line );
}

return YES;
}

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:

  1. Filter out emoji characters.
  2. 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.
  3. A comma or period at the end of a line counts as half width.
  4. After each line is laid out, spaces need to be considered and character x positions and widths are recalculated.
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
- (unsigned long)countCharInWidth:(unsigned short*)buff
rect:(QRRect*)char_rects
length:(unsigned long)len
maxWidth:(unsigned long)max_width
outWidth:(unsigned long*)pwidth
count:(unsigned long*)char_cnt
alignmeng:(unsigned int)text_align
{
unsigned long i;
unsigned long t;
signed long width = 0;
unsigned long count = 0;
double space_all;
double space_each;
bool break_line = false;

if ( nil == _setting || NULL == buff || NULL == pwidth || NULL == char_cnt )
return QR_FAILED;


if(char_rects == NULL)
{
for ( i = 0; '\0' != buff[i] && i < len; ++i )
{
// Filter out emoji characters.
if(buff[i]>=0xe000&&buff[i]<=0xe5ff)
buff[i] = 0x0020;//space

t = [self getCharWidth:buff[i]];

if ( width + t > max_width ) {
break;
}

width += t;
count += 1;
}
*pwidth = width;
*char_cnt = count;

[self reLayoutSkipHeadPunct:buff length:(unsigned)len count:char_cnt width:pwidth];

return QR_OK;
}

for ( i = 0; '\0' != buff[i] && i < len; ++i )
{
// Filter out emoji characters.
if(buff[i]>=0xe000 && buff[i]<=0xe5ff) buff[i] = 0x0020;//space

t = [self getCharWidth:buff[i]];

// Check whether this line is already full.
if ( width + t > max_width )
{
break_line = true;
break;
}

(char_rects+i)->x = width;
(char_rects+i)->w = t;

width += t;
count += 1;
}
*pwidth = width;
*char_cnt = count;

// If the text does not fill a line, return directly.
if (!break_line) return QR_OK;

// Punctuation rules for avoiding punctuation at line heads and tails:
// 1. 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.
// 2. 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.
// 3. If the next line starts with only one punctuation mark, move it up to the previous line.
[self reLayoutSkipHeadPunct:buff length:(unsigned)len count:char_cnt width:pwidth];

// A punctuation mark was added to the end of the line.
if(*char_cnt>count)
{
(char_rects+*char_cnt-1)->x = width;
(char_rects+*char_cnt-1)->w = *pwidth - width;
}

// A line-ending comma or full stop counts as half width.
if(buff[*char_cnt-1] == U_PUNCT_COMMA||
buff[*char_cnt-1] == U_PUNCT_FULLPOINT||
buff[*char_cnt-1] == U_PUNCT_PAUSE)
{
(char_rects+*char_cnt-1)->w /= 2;
*pwidth -= (char_rects+*char_cnt-1)->w;
}

// Recalculate character x positions and widths while accounting for spaces.
space_all = (double)max_width - (*pwidth);
space_each = space_all/(*char_cnt);

for (i = 0; i < *char_cnt ; i++)
{
(char_rects+i)->x += (space_each*i);
if(i > 0)
{
(char_rects+i-1)->w = (char_rects+i)->x - (char_rects+i-1)->x;
}
}
(char_rects+i-1)->w = max_width - (char_rects+i-1)->x;//last character width can't be forget


return QR_OK;
}

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
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
unsigned long qr_relayout_english_2(unsigned short * buff, 
unsigned long len,
unsigned long offsetX,
unsigned long * char_cnt )
{
signed long i;
unsigned long t;
unsigned long count = 0;

if ( NULL == buff || NULL == char_cnt ) return QR_FAILED;

i = *char_cnt;

if (i >= len || '\0' == buff[i] ) return QR_FAILED;

// If the first character of the next line is not a number or English letter,
// the current line can contain the last word normally, so return directly.
if (qr_is_english_digist_letter(buff[i]) == QR_FAILED) // lucas 1224
return QR_FAILED;

// Otherwise, if the first character of the next line is a number or English letter,
// count the length of the last word on the current line.
t = 0;
for ( i = (*char_cnt) - 1; i >= 0 && '\0' != buff[i] ; --i )
{
if (qr_is_english_digist_letter(buff[i]) == QR_FAILED)
if (qr_is_skip_punct_letter_tail_forbid(buff[i]) == QR_FAILED) {
break;
}
t++;
}
if (i < 0 && offsetX == 0 ) return QR_FAILED;

// Move the front part of the word to the next line.
count = *char_cnt;
count -= t;
*char_cnt = count;

// If we trace back to the start of the line, and the word already has more than 10 characters
// but still has not ended, restore it and do nothing.
if(*char_cnt == 0 && t > 10)//连续英文超过10个就断开 ericni 2012.10.09
*char_cnt += t;

return QR_OK;
}

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
2
3
4
5
6
TextPrgf_ptr_t custom_prgf = qr_alloc_prgf_space();
if (custom_prgf) {
custom_prgf->type = QR_TEXT_PRGF_TYPE_CUSTOM;
custom_prgf->size = 0;
custom_prgf->tail_index = i;
}

The insertion logic is as follows:

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
- (void)_insertPrgf:(TextPrgf_ptr_t)dstPrgf
beforePrgf:(TextPrgf_ptr_t)srcPrgf
atPrgfGroup:(TextPrgfGroup_ptr_t)prgfGroup
{
if (dstPrgf == NULL ||
srcPrgf == NULL ||
prgfGroup == NULL) {
return;
}

if (srcPrgf == _currPage.beginPrgf &&
_currPage.beginLine.ref != NULL &&
_currPage.beginLine.ref->prev == NULL) {
_currPage.beginPrgf = dstPrgf;
[self setFirstLine:_currPage.beginPrgf];
}

_nextPage.isValid = NO;
_prevPage.isValid = NO;

if (srcPrgf->prev == NULL) {
if (srcPrgf != prgfGroup->head) {
// src is not in prgfGroup.
//
return;
}

dstPrgf->prev = NULL;
dstPrgf->next = srcPrgf;
srcPrgf->prev = dstPrgf;
prgfGroup->head = dstPrgf;
}
else {
dstPrgf->prev = srcPrgf->prev;
dstPrgf->next = srcPrgf;
srcPrgf->prev = dstPrgf;
dstPrgf->prev->next = dstPrgf;
}

prgfGroup->count += 1;
}

Rendering

With all the preparation from the layout process, rendering becomes relatively simple:

  1. Prepare the canvas, pen, and color.
  2. Find the current page’s starting paragraph pointer and starting line pointer.
  3. 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
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
- (BOOL)repaint:(QRCanvas *)canvas rect:(QRRect *)rect
{
// Prepare various data.
...

// Start drawing.
[canvas drawTextBatchStart:0 length:0 destinationRect:0 alignment:align_flag];

// Set height range.
unsigned int yOffset = _docBoundRc.y;
unsigned int yOffsetMax = _docBoundRc.y+_docBoundRc.h-_fontHeight;

// Set drawing area.
[self recalc];
draw_rect.x = _docBoundRc.x;
draw_rect.y = yOffset;
draw_rect.w = _docBoundRc.w;
draw_rect.h = _fontHeight;

// Set pen color.
UIColor *lineColor = [QRThemeColorWithKey(kGlobalQRReadViewTextSelectionMainColor) getValue];

for (; yOffset < yOffsetMax && NULL != p_curr_prgf;)
{
if (QR_TEXT_PRGF_TYPE_SPACE == p_curr_prgf->type) {
// Ignore empty paragraph.
}
else if (QR_TEXT_PRGF_TYPE_TEXT == p_curr_prgf->type ||
QR_TEXT_PRGF_TYPE_AUTHOR == p_curr_prgf->type ||
QR_TEXT_PRGF_TYPE_BUSINISS_TEXT == p_curr_prgf->type)
{
// Get the line where drawing starts for a paragraph.
text_prgf = (TextPrgf_Text_ptr_t)p_curr_prgf;

if (p_curr_prgf == _currPrgf) {
p_curr_line = _currLine.ref;
}
else {
p_curr_line = text_prgf->first_line;
}

if (text_prgf->line_count <= 0) {
continue;
}

unsigned int curLineH = 0;
QRSetting *fontSetting = nil;

// Draw line by line.
for (; yOffset < yOffsetMax && NULL != p_curr_line;) {
draw_rect.y = yOffset;

if (QR_TEXT_PRGF_TYPE_AUTHOR == p_curr_prgf->type ||
QR_TEXT_PRGF_TYPE_BUSINISS_TEXT == p_curr_prgf->type) {
fontSetting = [self authorTipsSetting];
curLineH = [self authorTipsLineHeight];
[canvas setContentFont:[fontSetting getFontSize:FontState_Render] Type:[fontSetting getFontType:FontState_Render]];
[canvas setPenColor:textcolor];
}
else {
curLineH = _lineHeight;
[canvas setContentFont:[_setting getFontSize:FontState_Render] Type:[_setting getFontType:FontState_Render]];
fontSetting = _setting;
[canvas setPenColor:textcolor];
}

QRFont *currentFont = fontSetting.font_obj;
unsigned int currentFontHeight = 0;
[currentFont getHeight:&currentFontHeight];
draw_rect.h = currentFontHeight;

// Draw one line of text.
[canvas drawTextBatchDoing:(text_prgf->wide_buff + p_curr_line->offset)
inRect:(QRRect *)(text_prgf->char_rects + p_curr_line->offset)
length:p_curr_line->length
destinationRect:(QRRect *)&draw_rect
alignment:align_flag];

// Increase offset.
yOffset += curLineH;

// If it overlaps with a highlight range, draw the highlight.
// Full-text search highlighting goes here. Code omitted.
...

// Paragraph comment bubble drawing. Code omitted.
...

// Move to the next line.
p_curr_line = p_curr_line->next;
}

// Paragraph spacing offset.
if (p_curr_prgf->need_remove_para_space == 1) {
yOffset -= _lineSpace/2;
}else{
yOffset += _paraSpace;
}

}
else if (QR_TEXT_PRGF_TYPE_BOTTOMMENU == p_curr_prgf->type) {
// Draw bottom 4-tab entry. Code omitted.
}
else if (QR_TEXT_PRGF_TYPE_EXCELLENTPARACOMMENT == p_curr_prgf->type) {
// Draw "brilliant idea". Code omitted.
}
else if (QR_TEXT_PRGF_TYPE_CUSTOM == p_curr_prgf->type) {
// Custom module. Code omitted.
}
else {
break;
}
// Move to the next paragraph.
p_curr_prgf = p_curr_prgf->next;
}

// End drawing.
[canvas drawTextBatchEnd:0 length:0 destinationRect:0 alignment:0];

...

return YES;
}

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:

  1. Highlight areas need to be drawn, such as note underlines. So after each line is drawn, a check must be performed.
  2. At the end of each text paragraph, the engine checks whether a paragraph-comment bubble needs to be drawn.
  3. 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
2
3
4
- (BOOL)moveNextPage;
- (BOOL)movePrevPage;
- (BOOL)isTop;
- (BOOL)isBottom;

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.

  1. 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.
  2. 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 TxtPage was 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, isBottom also 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
2
3
4
5
6
@interface TxtPage : NSObject
@property (nonatomic, assign) TextPrgf_ptr_t beginPrgf;
@property (nonatomic, assign) LinePos_t beginLine;
@property (nonatomic, assign) TextPrgf_ptr_t endPrgf;
@property (nonatomic, assign) LinePos_t endLine
@end

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.

  1. In some cases, the chapter file is large and cannot be read entirely at once.
  2. 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
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
/**
* Function: whether the available cache from top to bottom is enough.
*/
- (BOOL)enoughUp2down:(TextPrgf_ptr_t)from_prgf cacheBytes:(unsigned long)cache_bytes
{
if(NULL == from_prgf) {
return NO;
}

if (NULL == _prgfGroup.tail) {
return NO;
}

// If it is already the last paragraph, identified by offset.
if (_prgfGroup.tail->offset + _prgfGroup.tail->size >= _fileSize) {
return YES;
}

// If it is already the last paragraph, identified by type.
if (_prgfGroup.tail->type == QR_TEXT_PRGF_TYPE_BOTTOMMENU) {
return YES;
}

// Determine whether the offset gap between the last paragraph and the current paragraph is greater than 8 * 1024.
long long temp_size = (long long)(_prgfGroup.tail->offset + _prgfGroup.tail->size) - (long long)(from_prgf->offset + from_prgf->size);
return temp_size >= (long long)cache_bytes;
}
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
/**
* Function: whether the available cache from bottom to top is enough.
*/
- (BOOL)enoughDown2up:(TextPrgf_ptr_t)from_prgf cacheBytes:(unsigned long)cache_bytes
{
unsigned long temp_size;

if (NULL == _prgfGroup.head) {
return 0;
}

if(NULL == from_prgf) {
return 0;
}

// If the current paragraph is already the first paragraph, there is no previous data to cache.
if (_prgfGroup.head->offset <= _docBOMSize) {
return 1;
}

// Determine whether the gap between the current paragraph offset and the first paragraph offset is greater than 8 * 1024.
temp_size = from_prgf->offset - _prgfGroup.head->offset;
return (temp_size >= cache_bytes ? 1 : 0);
}

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
2
- (void) recycleFromTop:(unsigned long) recycle_size;
- (void) recycleFromBottom:(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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static const unsigned short    __charset_spc[] =
{
// Half-width space, TAB, full-width space
0x0020,0x0009,0x3000
};
static const unsigned short __charset_1st[] =
{
// 第
0x7B2C
};
static const unsigned short __charset_2nd[] =
{
// 零一二三四五六七八九十百千零壹贰叁肆伍陆柒捌玖拾佰仟0123456789
0x96F6,0x4E00,0x4E8C,0x4E09,0x56DB,0x4E94,0x516D,0x4E03,0x516B,0x4E5D,
0x5341,0x767E,0x5343,0x96F6,0x58F9,0x8D30,0x53C1,0x8086,0x4F0D,0x9646,
0x67D2,0x634C,0x7396,0x62FE,0x4F70,0x4EDF,0x0030,0x0031,0x0032,0x0033,
0x0034,0x0035,0x0036,0x0037,0x0038,0x0039
};
static const unsigned short __charset_3rd[] =
{
// 章节回卷篇部
0x7AE0,0x8282,0x56DE,0x5377,0x7BC7,0x90E8
};

Summary

This article still has many shortcomings and will be improved later.

-------------本文结束 感谢您的阅读-------------
If this article helped you, your support encourages me to keep writing.

Title:How the TXT Engine Works

Author:lingyun

Published:2019-04-05 23:06

Updated:2026-09-23 00:37

Original link:https://tsuijunxi.github.io/en/2019/04/05/how-the-txt-engine-works/

License: Attribution-NonCommercial-NoDerivatives 4.0 International Please keep the original link and author when sharing.