1
0

EncodingScheme.c 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418
  1. /* vim: set expandtab ts=4 sw=4: */
  2. /*
  3. * You may redistribute this program and/or modify it under the terms of
  4. * the GNU General Public License as published by the Free Software Foundation,
  5. * either version 3 of the License, or (at your option) any later version.
  6. *
  7. * This program is distributed in the hope that it will be useful,
  8. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. * GNU General Public License for more details.
  11. *
  12. * You should have received a copy of the GNU General Public License
  13. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  14. */
  15. #include "benc/String.h"
  16. #include "benc/Dict.h"
  17. #include "memory/Allocator.h"
  18. #include "switch/EncodingScheme.h"
  19. #include "util/Bits.h"
  20. #include "util/Endian.h"
  21. #include "util/Hex.h"
  22. int EncodingScheme_getFormNum(struct EncodingScheme* scheme, uint64_t routeLabel)
  23. {
  24. if (scheme->count == 1) {
  25. return 0;
  26. }
  27. for (int i = 0; i < scheme->count; i++) {
  28. struct EncodingScheme_Form* form = &scheme->forms[i];
  29. Assert_true(form->prefixLen > 0 && form->prefixLen < 32);
  30. Assert_true(form->bitCount > 0 && form->bitCount < 32);
  31. if (0 == ((form->prefix ^ (uint32_t)routeLabel) << (32 - form->prefixLen))) {
  32. return i;
  33. }
  34. }
  35. return EncodingScheme_getFormNum_INVALID;
  36. }
  37. uint64_t EncodingScheme_convertLabel(struct EncodingScheme* scheme,
  38. uint64_t routeLabel,
  39. int convertTo)
  40. {
  41. int formNum = EncodingScheme_getFormNum(scheme, routeLabel);
  42. if (formNum == EncodingScheme_getFormNum_INVALID) {
  43. return EncodingScheme_convertLabel_INVALID;
  44. }
  45. struct EncodingScheme_Form* currentForm = &scheme->forms[formNum];
  46. if (scheme->count == 1
  47. || (routeLabel & Bits_maxBits64(currentForm->prefixLen + currentForm->bitCount)) == 1)
  48. {
  49. // fixed width encoding or it's a self label, this is easy
  50. switch (convertTo) {
  51. case 0:
  52. case EncodingScheme_convertLabel_convertTo_CANNONICAL: return routeLabel;
  53. default: return EncodingScheme_convertLabel_INVALID;
  54. }
  55. }
  56. routeLabel >>= currentForm->prefixLen;
  57. uint64_t director = routeLabel & Bits_maxBits64(currentForm->bitCount);
  58. routeLabel >>= currentForm->bitCount;
  59. // ACKTUNG: Magic afoot!
  60. // Conversions are necessary for two reasons.
  61. // #1 ensure 0001 always references interface 1, the self interface.
  62. // #2 reuse interface the binary encoding for interface 1 in other EncodingForms
  63. // because interface 1 cannot be expressed as anything other than 0001
  64. if ((currentForm->prefix & Bits_maxBits64(currentForm->prefixLen)) == 1) {
  65. // Swap 0 and 1 if the prefix is 1, this makes 0001 alias to 1
  66. // because 0 can never show up in the wild, we reuse it for 1.
  67. Assert_true(director != 0);
  68. if (director == 1) { director--; }
  69. } else if (director) {
  70. // Reuse the number 1 for 2 and 2 for 3 etc. to gain an extra slot in all other encodings.
  71. director++;
  72. }
  73. if (convertTo == EncodingScheme_convertLabel_convertTo_CANNONICAL) {
  74. // Take into account the fact that if the destination form does not have a 1 prefix,
  75. // an extra number will be available.
  76. int minBitsA = Bits_log2x64(director) + 1;
  77. int minBitsB = Bits_log2x64(director-1) + 1;
  78. for (int i = 0; i < scheme->count; i++) {
  79. struct EncodingScheme_Form* form = &scheme->forms[i];
  80. int minBits = ((form->prefix & Bits_maxBits64(form->prefixLen)) == 1)
  81. ? minBitsA : minBitsB;
  82. if (form->bitCount >= minBits) {
  83. convertTo = i;
  84. break;
  85. }
  86. }
  87. }
  88. if (convertTo < 0 || convertTo >= scheme->count) {
  89. // convertTo value is insane
  90. return EncodingScheme_convertLabel_INVALID;
  91. }
  92. struct EncodingScheme_Form* nextForm = &scheme->forms[convertTo];
  93. if ((nextForm->prefix & Bits_maxBits64(nextForm->prefixLen)) == 1) {
  94. // Swap 1 and 0 back if necessary.
  95. if (director == 0) { director++; }
  96. } else if (director) {
  97. // Or move the numbers down by one.
  98. director--;
  99. }
  100. if ((Bits_log2x64(director) + 1) > nextForm->bitCount) {
  101. // won't fit in requested form
  102. return EncodingScheme_convertLabel_INVALID;
  103. }
  104. if (Bits_log2x64(routeLabel) + EncodingScheme_formSize(nextForm) > 59) {
  105. return EncodingScheme_convertLabel_INVALID;
  106. }
  107. routeLabel <<= nextForm->bitCount;
  108. routeLabel |= director;
  109. routeLabel <<= nextForm->prefixLen;
  110. routeLabel |= nextForm->prefix;
  111. if ((routeLabel & Bits_maxBits64(nextForm->prefixLen + nextForm->bitCount)) == 1) {
  112. // looks like a self-route
  113. return EncodingScheme_convertLabel_INVALID;
  114. }
  115. return routeLabel;
  116. }
  117. /**
  118. * Decode a form from it's binary representation.
  119. * Can only use a maximum of 41 bits.
  120. *
  121. * @param out the output which will be populated with the encoding form data.
  122. * @param data the binary data in host order.
  123. * @return the number of bits of data which were consumed by the decoding.
  124. * If the content is definitely not an encoding form, 0 is returned.
  125. */
  126. static inline int decodeForm(struct EncodingScheme_Form* out, uint64_t d)
  127. {
  128. out->prefixLen = d & Bits_maxBits64(5);
  129. d >>= 5;
  130. int bitCount = d & Bits_maxBits64(5);
  131. if (bitCount < 1) {
  132. return 0;
  133. }
  134. out->bitCount = bitCount;
  135. d >>= 5;
  136. out->prefix = d & Bits_maxBits64(out->prefixLen);
  137. return 5 + 5 + out->prefixLen;
  138. }
  139. static inline int encodeForm(struct EncodingScheme_Form* in, uint64_t* data, int bits)
  140. {
  141. *data |= ((uint64_t)in->prefixLen & Bits_maxBits64(5)) << bits;
  142. bits += 5;
  143. *data |= ((uint64_t)in->bitCount & Bits_maxBits64(5)) << bits;
  144. bits += 5;
  145. *data |= ((uint64_t)in->prefix & Bits_maxBits64(in->prefixLen)) << bits;
  146. return 5 + 5 + in->prefixLen;
  147. }
  148. bool EncodingScheme_isSane(struct EncodingScheme* scheme)
  149. {
  150. // Check for obviously insane encoding.
  151. if (scheme->count == 0) {
  152. // No encoding schemes
  153. return false;
  154. }
  155. if (scheme->count > 31) {
  156. // impossible, each form must have a different bitCount and bitCount
  157. // can only be expressed in 5 bits limiting it to 31 bits max and a form
  158. // using zero bits is not allowed so there are only 31 max possibilities.
  159. return false;
  160. }
  161. if (scheme->count == 1) {
  162. // Fixed width encoding, prefix is not allowed and bitcount must be non-zero
  163. if (scheme->forms[0].prefixLen != 0 || scheme->forms[0].prefix != 0) {
  164. // prefixLen must be 0
  165. return false;
  166. }
  167. if (scheme->forms[0].bitCount == 0 || scheme->forms[0].bitCount > 31) {
  168. // bitcount must be non-zero and can't overflow the number
  169. return false;
  170. }
  171. return true;
  172. }
  173. // Variable width encoding.
  174. for (int i = 0; i < scheme->count; i++) {
  175. struct EncodingScheme_Form* form = &scheme->forms[i];
  176. if (form->prefixLen == 0 || form->prefixLen > 31) {
  177. // Prefix must exist in order to distinguish between forms
  178. return false;
  179. }
  180. if (form->bitCount == 0 || form->bitCount > 31) {
  181. // Bitcount must be non-zero
  182. return false;
  183. }
  184. if (EncodingScheme_formSize(form) > 59) {
  185. // cannot be represented in the usable space in a label
  186. return false;
  187. }
  188. if (i > 0 && form->bitCount <= scheme->forms[i-1].bitCount) {
  189. // Forms must be in ascending order.
  190. return false;
  191. }
  192. for (int j = 0; j < scheme->count; j++) {
  193. // Forms must be distinguishable by their prefixes.
  194. if (j != i
  195. && (scheme->forms[j].prefix & Bits_maxBits64(form->prefixLen)) == form->prefix)
  196. {
  197. return false;
  198. }
  199. }
  200. }
  201. return true;
  202. }
  203. List* EncodingScheme_asList(struct EncodingScheme* list, struct Allocator* alloc)
  204. {
  205. Assert_ifParanoid(EncodingScheme_isSane(list));
  206. String* prefixLen = String_new("prefixLen", alloc);
  207. String* bitCount = String_new("bitCount", alloc);
  208. String* prefix = String_new("prefix", alloc);
  209. List* scheme = List_new(alloc);
  210. for (int i = 0; i < (int)list->count; i++) {
  211. Dict* form = Dict_new(alloc);
  212. Dict_putInt(form, prefixLen, list->forms[i].prefixLen, alloc);
  213. Dict_putInt(form, bitCount, list->forms[i].bitCount, alloc);
  214. String* pfx = String_newBinary(NULL, 8, alloc);
  215. uint32_t prefix_be = Endian_hostToBigEndian32(list->forms[i].prefix);
  216. Hex_encode(pfx->bytes, 8, (uint8_t*)&prefix_be, 4);
  217. Dict_putString(form, prefix, pfx, alloc);
  218. List_addDict(scheme, form, alloc);
  219. }
  220. return scheme;
  221. }
  222. struct EncodingScheme* EncodingScheme_fromList(List* scheme, struct Allocator* alloc)
  223. {
  224. struct EncodingScheme* list = Allocator_malloc(alloc, sizeof(struct EncodingScheme));
  225. list->count = List_size(scheme);
  226. list->forms = Allocator_malloc(alloc, sizeof(struct EncodingScheme_Form) * list->count);
  227. for (int i = 0; i < (int)list->count; i++) {
  228. Dict* form = List_getDict(scheme, i);
  229. uint64_t* prefixLen = Dict_getInt(form, String_CONST("prefixLen"));
  230. uint64_t* bitCount = Dict_getInt(form, String_CONST("bitCount"));
  231. String* prefixStr = Dict_getString(form, String_CONST("prefix"));
  232. if (!prefixLen || !bitCount || !prefixStr || prefixStr->len != 8) {
  233. return NULL;
  234. }
  235. uint32_t prefix_be;
  236. if (Hex_decode((uint8_t*)&prefix_be, 4, prefixStr->bytes, 8) != 4) {
  237. return NULL;
  238. }
  239. list->forms[i].prefixLen = *prefixLen;
  240. list->forms[i].bitCount = *bitCount;
  241. list->forms[i].prefix = Endian_bigEndianToHost32(prefix_be);
  242. }
  243. if (!EncodingScheme_isSane(list)) {
  244. return NULL;
  245. }
  246. return list;
  247. }
  248. String* EncodingScheme_serialize(struct EncodingScheme* list,
  249. struct Allocator* alloc)
  250. {
  251. Assert_ifParanoid(EncodingScheme_isSane(list));
  252. // Create the string as the largest that is possible for the list size.
  253. String* out = String_newBinary(NULL, list->count * 6, alloc);
  254. int bits = 0;
  255. int outIndex = 0;
  256. uint64_t block = 0;
  257. for (int listIndex = 0; listIndex < (int)list->count; listIndex++) {
  258. bits += encodeForm(&list->forms[listIndex], &block, bits);
  259. while (bits > 8) {
  260. Assert_true(outIndex < (int)out->len);
  261. out->bytes[outIndex++] = (uint8_t) (block & 0xff);
  262. bits -= 8;
  263. block >>= 8;
  264. }
  265. }
  266. if (bits > 0) {
  267. out->bytes[outIndex++] = (uint8_t) (block & 0xff);
  268. }
  269. out->len = outIndex;
  270. return out;
  271. }
  272. struct EncodingScheme* EncodingScheme_deserialize(String* data,
  273. struct Allocator* alloc)
  274. {
  275. struct EncodingScheme_Form* forms = NULL;
  276. int outCount = 0;
  277. uint64_t block = 0;
  278. int bits = 0;
  279. int dataIndex = 0;
  280. for (;;) {
  281. // load data into the block from the incoming data source
  282. while (bits < 56 && dataIndex < (int)data->len) {
  283. block |= (((uint64_t)data->bytes[dataIndex++] & 0xff) << bits);
  284. bits += 8;
  285. }
  286. struct EncodingScheme_Form next;
  287. int ret = decodeForm(&next, block);
  288. bits -= ret;
  289. if (!ret || bits < 0) {
  290. if (block || dataIndex < (int)data->len || bits < 0) {
  291. // Invalid encoding
  292. return NULL;
  293. }
  294. break;
  295. }
  296. block >>= ret;
  297. Assert_true((next.prefix >> next.prefixLen) == 0);
  298. outCount += 1;
  299. forms = Allocator_realloc(alloc, forms, outCount * sizeof(struct EncodingScheme_Form));
  300. Bits_memcpyConst(&forms[outCount-1], &next, sizeof(struct EncodingScheme_Form));
  301. }
  302. struct EncodingScheme* out = Allocator_clone(alloc, (&(struct EncodingScheme) {
  303. .forms = forms,
  304. .count = outCount
  305. }));
  306. return EncodingScheme_isSane(out) ? out : NULL;
  307. }
  308. struct EncodingScheme* EncodingScheme_defineFixedWidthScheme(int bitCount, struct Allocator* alloc)
  309. {
  310. struct NumberCompress_FixedWidthScheme
  311. {
  312. struct EncodingScheme scheme;
  313. struct EncodingScheme_Form form;
  314. };
  315. struct NumberCompress_FixedWidthScheme* out =
  316. Allocator_malloc(alloc, sizeof(struct NumberCompress_FixedWidthScheme));
  317. struct NumberCompress_FixedWidthScheme scheme = {
  318. .scheme = { .count = 1, .forms = &out->form },
  319. .form = { .bitCount = bitCount, .prefixLen = 0, .prefix = 0, },
  320. };
  321. Bits_memcpyConst(out, &scheme, sizeof(struct NumberCompress_FixedWidthScheme));
  322. Assert_true(EncodingScheme_isSane(&out->scheme));
  323. return &out->scheme;
  324. }
  325. struct EncodingScheme* EncodingScheme_defineDynWidthScheme(struct EncodingScheme_Form* forms,
  326. int formCount,
  327. struct Allocator* alloc)
  328. {
  329. struct EncodingScheme_Form* formsCopy =
  330. Allocator_malloc(alloc, sizeof(struct EncodingScheme_Form) * formCount);
  331. Bits_memcpy(formsCopy, forms, sizeof(struct EncodingScheme_Form) * formCount);
  332. struct EncodingScheme* scheme = Allocator_clone(alloc, (&(struct EncodingScheme) {
  333. .count = formCount,
  334. .forms = formsCopy
  335. }));
  336. Assert_ifParanoid(EncodingScheme_isSane(scheme));
  337. return scheme;
  338. }
  339. int EncodingScheme_compare(struct EncodingScheme* a, struct EncodingScheme* b)
  340. {
  341. if (a->count == b->count) {
  342. return Bits_memcmp(a->forms, b->forms, sizeof(struct EncodingScheme_Form) * a->count);
  343. }
  344. return a->count > b->count ? 1 : -1;
  345. }
  346. /**
  347. * Return true if the route is to the switch's router interface.
  348. */
  349. int EncodingScheme_isSelfRoute(struct EncodingScheme* scheme, uint64_t routeLabel)
  350. {
  351. int formNum = EncodingScheme_getFormNum(scheme, routeLabel);
  352. if (formNum == EncodingScheme_getFormNum_INVALID) {
  353. return 0;
  354. }
  355. struct EncodingScheme_Form* currentForm = &scheme->forms[formNum];
  356. return (routeLabel & Bits_maxBits64(currentForm->prefixLen + currentForm->bitCount)) == 1;
  357. }
  358. int EncodingScheme_isOneHop(struct EncodingScheme* scheme, uint64_t routeLabel)
  359. {
  360. int fn = EncodingScheme_getFormNum(scheme, routeLabel);
  361. if (fn == EncodingScheme_getFormNum_INVALID) { return 0; }
  362. struct EncodingScheme_Form* form = &scheme->forms[fn];
  363. return (Bits_log2x64(routeLabel) == form->prefixLen + form->bitCount);
  364. }