docs/LMO.md

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