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.