<commit_before>QuickHelp Binary Format
=======================

This document describes the binary format of a QuickHelp .HLP file.


Overview
--------

A QuickHelp .HLP file comprises the following sections:

  +------------------------+
  |       File Header      |
  +------------------------+
  |      Topic offsets     |
  +------------------------+
  |     Context strings    |
  +------------------------+
  |     Context mapping    |
  +------------------------+
  |       Dictionary       |
  +------------------------+
  |      Huffman tree      |
  +------------------------+
  |      Topic[0] data     |
  +------------------------+
  |          ...           |
  +------------------------+
  |     Topic[N-1] data    |
  +------------------------+

Each section is described in detail below.

Note 1: All numeric fields are stored in little-endian order unless specified
        otherwise.

Note 2: Multiple help databases may be concatenated and stored in a single
        file. In this document, we assume a single database for convenience.


File Header
-----------

An HLP file starts with the "file header" section, which contains the 
following fields:

  Range   Type    Field                 Meaning
  ----------------------------------------------------------------------------
  00-02   WORD    Signature             format signature; must be 0x4C, 0x4E
  02-04   WORD    Unknown 1
  04-06   WORD    Attributes            bit 0: case-sensitivity of context
                                               strings
                                        bit 1: prevent the database from being
                                               decoded by the HELPMAKE utility
                                        bits 2-7: unknown
  06-07   BYTE    ControlCharacter      usually ':'; 0FFh also seen
  07-08   BYTE    Unknown 3
  08-0A   WORD    TopicCount            number of topics in the database
  0A-0C   WORD    ContextCount          number of context strings in the 
                                        database
  0C-0D   BYTE    DisplayWidth          width of the help viewer in characters
  0D-0E   BYTE    Unknown 4
  0E-10   WORD    Unknown 5
  10-1E   String  DatabaseName          database name used to resolve external
                                        links; NULL-terminated and NULL-padded
  1E-22   DWORD   reserved1             always 0
  22-26   DWORD   TopicOffsetsOffset    offset of topic offsets section
  26-2A   DWORD   ContextStringsOffset  offset of context strings section
  2A-2E   DWORD   ContextMappingOffset  offset of context mapping section
  2E-32   DWORD   DictionaryOffset      offset of dictionary section
  32-36   DWORD   HuffmanTreeOffset     offset of huffman tree section
  36-3A   DWORD   TopicDataOffset       offset of topic data section
  3A-3E   DWORD   reserved2             always 0
  3E-42   DWORD   reserved3             always 0
  42-46   DWORD   DatabaseSize          size of the help database in bytes


Topic Offsets
-------------

The "topic offsets" section comprises (TopicCount + 1) DWORD integers. The
first (TopicCount) integers specify the offset of the corresponding topics
relative to the beginning of the help database. The last integer specifies
the offset just past the end of the last topic.

The size (in bytes) of topic k can be found by computing the difference
between TopicOffset[k] and TopicOffset[k+1].

   (N = TopicCount)
  +--------------------+
  |   TopicOffset[0]   |   (DWORD) offset of the first topic
  +--------------------+
  |        ...         |   ...
  +--------------------+
  |  TopicOffset[N-1]  |   (DWORD) offset of the last topic
  +--------------------+
  |   TopicOffset[N]   |   (DWORD) indicates the end of the last topic;
  +--------------------+           should be equal to DatabaseSize.

        
Context strings
---------------

The "context strings" section comprises (ContextCount) NULL-terminated context
strings. The context strings are not sorted.

   (N = ContextCount)
  +--------------------+
  |  ContextString[0]  |   first context string (NULL-terminated)
  +--------------------+
  |        ...         |   ...
  +--------------------+
  | ContextString[N-1] |   last context string (NULL-terminated)
  +--------------------+


Context mapping
---------------

The "context mapping" section comprises (ContextCount) WORD integers. Each
integer specifies the index of the topic to which this context string
resolves, and must be within the range 0 to (TopicCount-1) inclusive.

   (N = ContextCount)
  +-------------------+
  |  ContextTopic[0]  |   (WORD) topic index that owns first context string
  +-------------------+
  |        ...        |   ...
  +-------------------+
  | ContextTopic[N-1] |   (WORD) topic index that owns last context string
  +-------------------+


Dictionary
----------

The "dictionary" section contains a list of frequently used words in the help
database. It is used by the dictionary substitution stage of compressing the
database.

Each word is prefixed by a byte that indicates the length of the word in
bytes, excluding the prefix. The word is NOT NULL-terminated.

   (N = implied)
  +-------------+
  |   Word[0]   |   first word in dictionary (length-prefixed string)
  +-------------+
  |     ...     |   ...
  +-------------+
  |  Word[N-1]  |   last word in dictionary (length-prefixed string)
  +-------------+

There can be at most 1024 (10 bits) words in the dictionary; but there can be
fewer. The number of words is not explicitly specified and must be implied by
reading the entire section between [DictionaryOffset, HuffmanTreeOffset).


Huffman tree
------------

The "huffman tree" section contains the huffman tree used by the huffman
compression pass.

Each node in a huffman tree is either a leaf node or an internal node. A leaf
node represents a symbol valued from 0 to 255. An internal node must have two
children and encodes a bit in the huffman code: the left child encodes 0 and
the right child encodes 1.

511 nodes are sufficient to encode all 256 symbols. If the tree contains less
than 511 nodes, only a subset of the 256 symbols is encoded.

The huffman tree is compactly stored in an array of WORD integers, where each
integer represents a node. The array is terminated by an extra WORD of value
zero. The nodes plus the terminating 0 WORD should match the length of the
section specified by [HuffmanTreeOffset, TopicDataOffset).

The storage format of the huffman tree is as follows. Denote the nodes in the
tree by Node[0] through Node[N] where N <= 511 and Node[N] == 0. Then:
  - A leaf node, Node[i], has its highest bit set to 1, and the symbol it
    represents is stored in the low byte of Node[i].
  - An internal node, Node[i], has its highest is set to 0, and
    o its right child (1 bit) is Node[i+1];
    o its left child (0 bit) is Node[Node[i]/2].
  - The root node is Node[0]. It must be an internal node.

Note that this format is not restricted to a huffman tree; it can be used to
store any proper binary tree.

The above node numbering scheme can be generated by performing a right-to-left
pre-order traversal of the tree and number the node sequentially as they are
visited.


Topic data
----------

Following the huffman tree are N blocks of topic data, each corresponding to
a topic. Each topic is separately compressed. The compression method is
described below.

Topic content is transformed and compressed in three steps:

Step 1. Topic content is converted from QuickHelp markup format to a binary
        format suitable for screen display.

Step 2. The binary data is compressed using dictionary substitution and
        run-length encoding.

Step 3. The compressed data is encoded with huffman coding and stored in the
        help database.

The following chart summarizes this procedure:

  +=====================+
  |  Topic Text Markup  |
  +=====================+
             |
             |  [1] convert to binary
             v
  +=====================+
  |  Binary Topic Data  |
  +=====================+
             |
             |  [2] dictionary substitution
             |      and run-length encoding
             v
  +=====================+
  | Compact Topic Data  |
  +=====================+
             |
             |  [3] huffman encoding
             v
  +=====================+
  |   Data in Storage   |
  +=====================+


Step 1: Convert QuickHelp Markup format to binary format
--------------------------------------------------------

The QuickHelp markup format is described in detail in MASM documentation,
Chapter 18 - Creating Help Files With HELPMAKE.

The QuickHelp binary format is the format that is actually used by the help
system to display help content and interact with the user.

In the QuickHelp binary format, each line is represented by two parts:
  1. Text
  2. Styles and links

"Text" is the characters displayed on the screen, stripped of any formatting
information.

"Styles" associate each character with one or more of the following styles:
bold, italic, and underline. In QuickHelp viewer, the styles are rendered as
follows:

  Value  Style                   Foreground Color      Background Color
  ---------------------------------------------------------------------
  0      Normal (default)        white                 black
  1      Bold                    highlighted white     black
  2      Italic                  green                 black
  3      Bold+Italic             cyan                  black
  4      Underline               red                   black
  5      Bold+Underline          highlighted white     cyan
  6      Italic+Underline        white                 black
  7      Bold+Italic+Underline   black                 black

"Links" associate a range of characters in a line with a link target. The link
target must take one of the following forms:

  1. a context string that matches a context in the current help database or
     another help database, or

  2. a 16-bit integer with the highest bit set, whose lowest 15 bits specifies
     a topic index in the current help database.

Links are defined orthogonal to styles. Links must not overlap.

With this model in mind, below we describe the QuickHelp binary format.

Each topic is first split into lines. Colon commands (see MASM docs for a
detailed description) are treated as plain text when stored. Each line
consists of a text block and an attribute block, like below:

  +-----------------+
  | TextBlockLen(X) |   1 byte     number of bytes in text block, including
  +-----------------+              the "TextBlockLen" byte
  .                 .
  .  TextBlockData  .   X-1 bytes  characters in the line, stripped of any
  .                 .              formatting information
  +-----------------+
  | AttrBlockLen(Y) |   1 byte     number of bytes in attribute block,
  +-----------------+              including the "AttrBlockLen" byte
  .                 .
  .  AttrBlockData  .   Y-1 bytes  character style and link information; see
  .                 .              below.
  +-----------------+

"TextBlockLen" and "AttrBlockLen" must be greater than zero.

"TextBlockData" is the plain text to display. Each byte corresponds to an
ASCII or Extended ASCII character; on Windows, this is code page 437. Note,
however, that characters 0-31 are rendered as graphic characters instead of
interpreted as control characters when displayed in QuickHelp; this means
that a further mapping must be performed after transforming using CP-437.

"AttrBlockData" comprises a mandatory "Styles" part followed by an optional
"Links" part. 

If no link exists in a line, the format of "AttrBlockData" is

   (Y-1) bytes
  +==========+
  |  Styles  |
  +==========+

If links are present in a line, the format of "AttrBlockData" is

   (? bytes)  1 byte (? bytes)  --> total (Y-1) bytes
  +==========+------+=========+
  |  Styles  | 0xFF |  Links  |
  +==========+------+=========+

"Styles" is an alternating list of "chunk length" and "style", as follows:

  +--------------+
  |  ChunkLen 0  |   1 byte
  +--------------+
  |    Style 1   |   1 byte
  +--------------+
  |  ChunkLen 1  |   1 byte
  +--------------+
  |    Style 2   |   1 byte
  +--------------+
  |  ChunkLen 2  |   1 byte
  +--------------+
  ~     ...      ~   ...
  +--------------+

This list always starts with a ChunkLen[0] field. The default style applies
to the first (ChunkLen[0]) characters in the line. The next ChunkLen[1] 
characters apply the style defined in Style[1]. Following that, the next
ChunkLen[2] characters apply the style defined in Style[2]; and so on.

Each Style byte comprises the following bits:

    7   6   5   4   3   2   1   0
  +---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 0 | U | I | B |
  +---+---+---+---+---+---+---+---+
    |_______________|   |   |   |---- Bold
            |           |   |-------- Italic
        reserved;       |------------ Underline
        must be 0.

Each Style[i] field replaces the previous style; the style bits are not merged
or toggled.

"Links" is an array of variable-length records, where each record defines a
link in the line. The format of a record is:

  +--------------+
  |  StartIndex  |   1 byte   ONE-based index of the first character in the
  +--------------+            link, inclusive.
  |   EndIndex   |   1 byte   ONE-based index of the last character in the
  +--------------+            link, inclusive.
  |   Context    |   ? bytes  NULL-terminated context string that specifies
  |    String    |            the link target, or an empty string to indicate
  +--------------+            that TopicIndex should be used as the target.
  |  TopicIndex  |     WORD   Optional; present only if ContextString is empty
  +--------------+


Step 2: Dictionary substitution and run-length encoding
-------------------------------------------------------

The compressed data is a byte stream that has the following format.
<commit_msg>Update format description to use the terms used in HELPMAKE.<commit_after>QuickHelp Binary Format
=======================

This document describes the binary format of a QuickHelp .HLP file.


Overview
--------

A QuickHelp .HLP file comprises the following sections:

  +------------------------+
  |       File Header      |
  +------------------------+
  |       Topic Index      |
  +------------------------+
  |     Context Strings    |
  +------------------------+
  |       Context Map      |
  +------------------------+
  |        Keywords        |
  +------------------------+
  |      Huffman Tree      |
  +------------------------+
  |      Topic[0] Text     |
  +------------------------+
  |          ...           |
  +------------------------+
  |     Topic[N-1] Text    |
  +------------------------+

Each section is described in detail below.

Note 1: All numeric fields are stored in little-endian order unless specified
        otherwise.

Note 2: Multiple help databases may be concatenated and stored in a single
        file. In this document, we assume a single database for convenience.


File Header
-----------

An HLP file starts with the File Header section, which is a structure with the
following fields:

  Range   Type    Field                 Meaning
  ----------------------------------------------------------------------------
  00-02   WORD    Signature             format signature; must be 0x4C, 0x4E
  02-04   WORD    Unknown 1             may be version; always 2
  04-06   WORD    Attributes            bit 0: case-sensitivity of context
                                               strings
                                        bit 1: prevent the database from being
                                               decoded by the HELPMAKE utility
                                        bits 2-7: unknown
  06-07   BYTE    ControlCharacter      usually ':'; 0FFh also seen
  07-08   BYTE    Unknown 3
  08-0A   WORD    TopicCount            number of topics in the database
  0A-0C   WORD    ContextCount          number of context strings in the 
                                        database
  0C-0D   BYTE    DisplayWidth          width of the help viewer in characters
  0D-0E   BYTE    Unknown 4
  0E-10   WORD    Unknown 5
  10-1E   BYTE[]  DatabaseName          database name used to resolve external
                                        links; NULL-terminated and NULL-padded
  1E-22   DWORD   reserved1             always 0
  22-26   DWORD   TopicIndex            offset of the Topic Index section
  26-2A   DWORD   ContextStringsOffset  offset of the Context Strings section
  2A-2E   DWORD   ContextMapOffset      offset of the Context Mapping section
  2E-32   DWORD   KeywordsOffset        offset of the Keywords section;
                                        0 if keyword compression is not used
  32-36   DWORD   HuffmanTreeOffset     offset of the Huffman Tree section;
                                        0 if Huffman compression is not used
  36-3A   DWORD   TopicTextOffset       offset of the start of topic texts
  3A-3E   DWORD   reserved2             always 0
  3E-42   DWORD   reserved3             always 0
  42-46   DWORD   DatabaseSize          size of the help database in bytes


Topic Index
-----------

The Topic Index section comprises (TopicCount + 1) DWORD integers. The first
TopicCount integers specify the offset of the corresponding topic texts
relative to the beginning of the help database. The last integer specifies
the offset just past the end of the last topic.

   (N = TopicCount)
  +--------------------+
  |   TopicOffset[0]   |   (DWORD) offset of the first topic
  +--------------------+
  |        ...         |   ...
  +--------------------+
  |  TopicOffset[N-1]  |   (DWORD) offset of the last topic
  +--------------------+
  |   TopicOffset[N]   |   (DWORD) indicates the end of the last topic;
  +--------------------+           should be equal to DatabaseSize.

The size (in bytes) of topic k can be found by computing the difference
between TopicOffset[k] and TopicOffset[k+1].

        
Context Strings
---------------

The Context Strings section comprises (ContextCount) NULL-terminated context
strings. The context strings are not sorted.

   (N = ContextCount)
  +--------------------+
  |  ContextString[0]  |   first context string (NULL-terminated)
  +--------------------+
  |        ...         |   ...
  +--------------------+
  | ContextString[N-1] |   last context string (NULL-terminated)
  +--------------------+


Context Map
-----------

The Context Map section comprises (ContextCount) WORD integers. Each integer
specifies the index of the topic to which the corresponding context string
resolves, and must be within the range 0 to (TopicCount-1) inclusive.

   (N = ContextCount)
  +-------------------+
  |   ContextMap[0]   |   (WORD) index of the topic that the first context
  +-------------------+          string points to
  |        ...        |   ...
  +-------------------+
  |  ContextMap[N-1]  |   (WORD) index of the topic that the last context
  +-------------------+          string points to


Keywords
--------

The Keywords section contains a list of frequently used words in the topics.
It is used by the keyword compression (dictionary substitution) pass. This
section does not exist if keyword compression is not used for this database.

Each word is prefixed by a byte that specifies the length of the word in
bytes, not counting the prefix itself. The word is NOT NULL-terminated.

   (N = implied)
  +-------------+
  |   Word[0]   |   first word in dictionary (length-prefixed string)
  +-------------+
  |     ...     |   ...
  +-------------+
  |  Word[N-1]  |   last word in dictionary (length-prefixed string)
  +-------------+

There can be at most 1024 (10 bits) words in the dictionary; but there can be
fewer. The number of words is not explicitly specified and must be implied by
reading the entire section.


Huffman Tree
------------

The Huffman Tree section contains the huffman tree used by the Huffman
compression pass. This section does not exist if Huffman compression is not
used for this database.

Each node in a huffman tree is either a leaf node or an internal node. A leaf
node represents a symbol valued from 0 to 255. An internal node must have two
children and encodes a bit in the huffman code: the left child encodes 0 and
the right child encodes 1.

511 nodes are sufficient to encode all 256 symbols. If the tree contains less
than 511 nodes, only a subset of the 256 symbols are encoded.

The Huffman tree is compactly stored in an array of WORD integers, where each
integer represents a node. The array is terminated by an extra WORD of value
zero. The nodes plus the terminating 0 WORD should match the length of the
section specified by [HuffmanTreeOffset, TopicTextOffset).

The storage format of the Huffman tree is as follows. Denote the nodes in the
tree by Node[0] through Node[N] where N <= 511 and Node[N] == 0. Then:

  - A leaf node, Node[i], has its highest bit set to 1, and the symbol it
    represents is stored in the low byte of Node[i].

  - An internal node, Node[i], has its highest is set to 0, and
    o its right child (1 bit) is Node[i+1];
    o its left child (0 bit) is Node[Node[i]/2].

  - The root node is Node[0]. It must be an internal node.

Note that this format is not specific to a Huffman tree; it can be used to
store any proper binary tree.

The above node numbering scheme can be generated by performing a right-to-left
pre-order traversal of the tree and number the node sequentially as they are
visited.


Topic Text
----------

Following the meta data sections are N blocks of topic texts. Each topic is
separately compressed. The compression method is described below.

Topic text is transformed, compressed, and encoded in three steps:

  Step 1. Topic text is transformed from QuickHelp markup format to a binary
          format.

  Step 2. The binary topic data is compressed using keyword compression and
          run-length encoding.

  Step 3. The compressed data is encoded with Huffman coding and stored in
          the help database.

The following diagram summarizes this procedure:

  +=====================+
  |  Markup Topic Data  |
  +=====================+
             |
             |  [1] transform to binary
             v
  +=====================+
  |  Binary Topic Data  |
  +=====================+
             |
             |  [2] keyword compression and
             |      run-length encoding
             v
  +=====================+
  | Compact Topic Data  |
  +=====================+
             |
             |  [3] Huffman encoding
             v
  +=====================+
  | Encoded Topic Data  |
  +=====================+


Step 1: Convert QuickHelp Markup format to binary format
--------------------------------------------------------

The QuickHelp markup format is described in detail in MASM documentation,
Chapter 18 - Creating Help Files With HELPMAKE.

The QuickHelp binary format is the format that is actually used by the help
system to display help content and interact with the user.

In the QuickHelp binary format, each line is represented by two parts:
  1. Text
  2. Styles and links

"Text" is the characters displayed on the screen, stripped of any formatting
information.

"Styles" associate each character with one or more of the following styles:
bold, italic, and underline. In QuickHelp viewer, the styles are rendered as
follows:

  Value  Style                   Foreground Color      Background Color
  ---------------------------------------------------------------------
  0      Normal (default)        white                 black
  1      Bold                    highlighted white     black
  2      Italic                  green                 black
  3      Bold+Italic             cyan                  black
  4      Underline               red                   black
  5      Bold+Underline          highlighted white     cyan
  6      Italic+Underline        white                 black
  7      Bold+Italic+Underline   black                 black

"Links" associate a range of characters in a line with a link target. The link
target must take one of the following forms:

  1. a context string that matches a context in the current help database or
     another help database, or

  2. a 16-bit integer with the highest bit set, whose lowest 15 bits specifies
     a topic index in the current help database.

Links are defined orthogonal to styles. Links must not overlap.

With this model in mind, below we describe the QuickHelp binary format.

Each topic is first split into lines. Colon commands (see MASM docs for a
detailed description) are treated as plain text when stored. Each line
consists of a text block and an attribute block, like below:

  +-----------------+
  | TextBlockLen(X) |   1 byte     number of bytes in text block, including
  +-----------------+              the "TextBlockLen" byte
  .                 .
  .  TextBlockData  .   X-1 bytes  characters in the line, stripped of any
  .                 .              formatting information
  +-----------------+
  | AttrBlockLen(Y) |   1 byte     number of bytes in attribute block,
  +-----------------+              including the "AttrBlockLen" byte
  .                 .
  .  AttrBlockData  .   Y-1 bytes  character style and link information; see
  .                 .              below.
  +-----------------+

"TextBlockLen" and "AttrBlockLen" must be greater than zero.

"TextBlockData" is the plain text to display. Each byte corresponds to an
ASCII or Extended ASCII character; on Windows, this is code page 437. Note,
however, that characters 0-31 are rendered as graphic characters instead of
interpreted as control characters when displayed in QuickHelp; this means
that a further mapping must be performed after transforming using CP-437.

"AttrBlockData" comprises a mandatory "Styles" part followed by an optional
"Links" part. 

If no link exists in a line, the format of "AttrBlockData" is

   (Y-1) bytes
  +==========+
  |  Styles  |
  +==========+

If links are present in a line, the format of "AttrBlockData" is

   (? bytes)  1 byte (? bytes)  --> total (Y-1) bytes
  +==========+------+=========+
  |  Styles  | 0xFF |  Links  |
  +==========+------+=========+

"Styles" is an alternating list of "chunk length" and "style", as follows:

  +--------------+
  |  ChunkLen 0  |   1 byte
  +--------------+
  |    Style 1   |   1 byte
  +--------------+
  |  ChunkLen 1  |   1 byte
  +--------------+
  |    Style 2   |   1 byte
  +--------------+
  |  ChunkLen 2  |   1 byte
  +--------------+
  ~     ...      ~   ...
  +--------------+

This list always starts with a ChunkLen[0] field. The default style applies
to the first (ChunkLen[0]) characters in the line. The next ChunkLen[1] 
characters apply the style defined in Style[1]. Following that, the next
ChunkLen[2] characters apply the style defined in Style[2]; and so on.

Each Style byte comprises the following bits:

    7   6   5   4   3   2   1   0
  +---+---+---+---+---+---+---+---+
  | 0 | 0 | 0 | 0 | 0 | U | I | B |
  +---+---+---+---+---+---+---+---+
    |_______________|   |   |   |---- Bold
            |           |   |-------- Italic
        reserved;       |------------ Underline
        must be 0.

Each Style[i] field replaces the previous style; the style bits are not merged
or toggled.

"Links" is an array of variable-length records, where each record defines a
link in the line. The format of a record is:

  +--------------+
  |  StartIndex  |   1 byte   ONE-based index of the first character in the
  +--------------+            link, inclusive.
  |   EndIndex   |   1 byte   ONE-based index of the last character in the
  +--------------+            link, inclusive.
  |   Context    |   ? bytes  NULL-terminated context string that specifies
  |    String    |            the link target, or an empty string to indicate
  +--------------+            that TopicIndex should be used as the target.
  |  TopicIndex  |     WORD   Optional; present only if ContextString is empty
  +--------------+


Step 2: Keyword compression and run-length encoding
---------------------------------------------------

The compressed data is a byte stream that has the following format.

{'fraction_non_alphanumeric': 0.15393290104313503, 'fraction_numerical': 0.015118409923879335, 'mean_word_length': 1.702828840841985, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4103312', 'n_tokens_mistral': 7571, 'n_tokens_neox': 6946, 'n_words': 3268}