Merge pull request #1596 from stangri/luci-app-vpnbypass
[oweals/luci.git] / documentation / LMO.md
1 LMO is a simple binary format to pack language strings into a more efficient form. Although it's suitable to store any kind of key-value table, it's only used for the LuCI *.po based translation system at the moment. The abbreviation "LMO" stands for "Lua Machine Objects" in the style of the GNU gettext *.mo format.
2
3
4 # Format Specification
5
6 A LMO file is divided into two parts: the payload and the index lookup table.
7 All segments of the file are 4 Byte aligned to ease reading and processing of the format.
8 Only unsigned 32bit integers are used and stored in network byte order, so an implementation has to use htonl() to properly read them.
9
10 Schema:
11         
12         <file:
13           <payload:
14             <entry #1: 4 byte aligned data>
15         
16             <entry #2: 4 byte aligned data>
17         
18             ...
19         
20             <entry #N: 4 byte aligned data>
21           >
22         
23           <index table:
24             <entry #1:
25               <uint32_t: hash of the first key>
26               <uint32_t: hash of the first value>
27               <uint32_t: file offset of the first value>
28               <uint32_t: length of the first value>
29             >
30         
31             <entry #2:
32               <uint32_t: hash of the second key>
33               <uint32_t: hash of the second value>
34               <uint32_t: file offset of the second value>
35               <uint32_t: length of the second value>
36             >
37         
38             ...
39         
40             <entry #N:
41               <uint32_t: hash of the Nth key>
42               <uint32_t: hash of the Nth value>
43               <uint32_t: file offset of the Nth value>
44               <uint32_t: length of the Nth value>
45             >
46           >
47         
48           <uint32_t: offset of the begin of index table>
49         >
50         
51
52
53 # Processing
54
55 In order to process a LMO file, an implementation would have to do the following steps:
56
57 ## Read Index
58
59 1. Locate and open the archive file
60 1. Seek to end of file - 4 bytes (sizeof(uint32_t))
61 1. Read 32bit index offset and swap from network to native byte order
62 1. Seek to index offset, calculate index length: filesize - index offset - 4
63 1. Initialize a linked list for index table entries
64 1. Read each index entry until the index length is reached, read and byteswap 4 * uint32_t for each step
65 1. Seek to begin of file
66
67 ## Read Entry
68
69 1. Calculate the unsigned 32bit hash of the entries key value (see "Hash Function" section below)
70 1. Obtain the archive index
71 1. Iterate through the linked index list, perform the following steps for each entry:
72   1. Compare the entry hash value with the calculated hash from step 1
73   2. If the hash values are equal proceed with step 4
74   3. Select the next entry and repeat from step 3.1
75 1. Seek to the file offset specified in the selected entry
76 1. Read as much bytes as specified in the entry length into a buffer
77 1. Return the buffer value
78
79 # Hash Function
80
81 The current LuCI-LMO implementation uses the "Super Fast Hash" function which was kindly put in the public domain by it's original author. See http://www.azillionmonkeys.com/qed/hash.html for details. Below is the C-Implementation of this function:
82
83         
84         #if (defined(__GNUC__) && defined(__i386__))
85         #define sfh_get16(d) (*((const uint16_t *) (d)))
86         #else
87         #define sfh_get16(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
88                                                    +(uint32_t)(((const uint8_t *)(d))[0]) )
89         #endif
90         
91         uint32_t sfh_hash(const char * data, int len)
92         {
93                 uint32_t hash = len, tmp;
94                 int rem;
95         
96                 if (len <= NULL) return 0;
97         
98                 rem = len & 3;
99                 len >>= 2;
100         
101                 /* Main loop */
102                 for (;len > 0; len--) {
103                         hash  += sfh_get16(data);
104                         tmp    = (sfh_get16(data+2) << 11) ^ hash;
105                         hash   = (hash << 16) ^ tmp;
106                         data  += 2*sizeof(uint16_t);
107                         hash  += hash >> 11;
108                 }
109         
110                 /* Handle end cases */
111                 switch (rem) {
112                         case 3: hash += sfh_get16(data);
113                                 hash ^= hash << 16;
114                                 hash ^= data[sizeof(uint16_t)] << 18;
115                                 hash += hash >> 11;
116                                 break;
117                         case 2: hash += sfh_get16(data);
118                                 hash ^= hash << 11;
119                                 hash += hash >> 17;
120                                 break;
121                         case 1: hash += *data;
122                                 hash ^= hash << 10;
123                                 hash += hash >> 1;
124                 }
125         
126                 /* Force "avalanching" of final 127 bits */
127                 hash ^= hash << 3;
128                 hash += hash >> 5;
129                 hash ^= hash << 4;
130                 hash += hash >> 17;
131                 hash ^= hash << 25;
132                 hash += hash >> 6;
133         
134                 return hash;
135         }
136         
137
138 # Reference Implementation
139
140 A reference implementation can be found here:
141 http://luci.subsignal.org/trac/browser/luci/trunk/libs/lmo/src
142
143 The lmo_po2lmo.c executable implements a *.po to *.lmo conversation utility and lmo_lookup.c is a simple *.lmo test utility.
144 Lua bindings for lmo are defined in lmo_lualib.c and associated headers.