EncodingScheme.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512
  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 <https://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. bool EncodingScheme_is358(struct EncodingScheme* scheme)
  38. {
  39. struct EncodingScheme_Form v358[3] = {
  40. { .bitCount = 3, .prefixLen = 1, .prefix = 1, },
  41. { .bitCount = 5, .prefixLen = 2, .prefix = 1<<1, },
  42. { .bitCount = 8, .prefixLen = 2, .prefix = 0, }
  43. };
  44. if (scheme->count != 3) { return false; }
  45. for (int i = 0; i < 3; i++) {
  46. if (Bits_memcmp(&v358[i], &scheme->forms[i], sizeof(struct EncodingScheme_Form))) {
  47. return false;
  48. }
  49. }
  50. return true;
  51. }
  52. int EncodingScheme_parseDirector(struct EncodingScheme* scheme, uint64_t label)
  53. {
  54. int formNum = EncodingScheme_getFormNum(scheme, label);
  55. if (formNum == EncodingScheme_getFormNum_INVALID) {
  56. return EncodingScheme_parseDirector_INVALID;
  57. }
  58. struct EncodingScheme_Form* currentForm = &scheme->forms[formNum];
  59. int dir = (label >> currentForm->prefixLen) & Bits_maxBits64(currentForm->bitCount);
  60. if (!EncodingScheme_is358(scheme)) {
  61. // use ^1 to flip slots 0 and 1 in variable width schemes
  62. return dir ^ (scheme->count > 1);
  63. } else {
  64. // slot 0 must always be represented as a 1, so in 358, 0 and 1 are swapped.
  65. if (formNum > 0) {
  66. dir += (dir > 0);
  67. } else {
  68. dir += (dir == 0) - (dir == 1);
  69. }
  70. return dir;
  71. }
  72. }
  73. uint64_t EncodingScheme_serializeDirector(struct EncodingScheme* scheme, int dir, int formNum)
  74. {
  75. if (!EncodingScheme_is358(scheme)) {
  76. if (formNum < 0) {
  77. for (formNum = 0; formNum < scheme->count; formNum++) {
  78. if (!(dir >> scheme->forms[formNum].bitCount)) { break; }
  79. }
  80. }
  81. // use ^1 to flip slots 0 and 1 in variable width schemes
  82. dir ^= (scheme->count > 1);
  83. } else {
  84. if (formNum < 0) {
  85. for (formNum = 0; formNum < scheme->count; formNum++) {
  86. if (!((dir - (!!formNum)) >> scheme->forms[formNum].bitCount)) { break; }
  87. }
  88. }
  89. if (formNum) {
  90. // slot 1 is only represented in form 0 so in all other forms, it is skipped.
  91. dir -= (dir > 0);
  92. } else {
  93. // slot 0 must always be represented as a 1, so 0 and 1 are swapped.
  94. dir += (dir == 0) - (dir == 1);
  95. }
  96. }
  97. if (formNum >= scheme->count) { return ~0ull; }
  98. struct EncodingScheme_Form* f = &scheme->forms[formNum];
  99. return (dir << f->prefixLen) | f->prefix;
  100. }
  101. uint64_t EncodingScheme_convertLabel(struct EncodingScheme* scheme,
  102. uint64_t routeLabel,
  103. int convertTo)
  104. {
  105. int formNum = EncodingScheme_getFormNum(scheme, routeLabel);
  106. if (formNum == EncodingScheme_getFormNum_INVALID) {
  107. return EncodingScheme_convertLabel_INVALID;
  108. }
  109. struct EncodingScheme_Form* currentForm = &scheme->forms[formNum];
  110. if (scheme->count == 1
  111. || (routeLabel & Bits_maxBits64(currentForm->prefixLen + currentForm->bitCount)) == 1)
  112. {
  113. // fixed width encoding or it's a self label, this is easy
  114. switch (convertTo) {
  115. case 0:
  116. case EncodingScheme_convertLabel_convertTo_CANNONICAL: return routeLabel;
  117. default: return EncodingScheme_convertLabel_INVALID;
  118. }
  119. }
  120. routeLabel >>= currentForm->prefixLen;
  121. uint64_t director = routeLabel & Bits_maxBits64(currentForm->bitCount);
  122. routeLabel >>= currentForm->bitCount;
  123. // ACKTUNG: Magic afoot!
  124. // Conversions are necessary for two reasons.
  125. // #1 ensure 0001 always references interface 1, the self interface.
  126. // #2 reuse interface the binary encoding for interface 1 in other EncodingForms
  127. // because interface 1 cannot be expressed as anything other than 0001
  128. if (!EncodingScheme_is358(scheme)) {
  129. // don't pull this bug-workaround crap for sane encodings schemes.
  130. } else if ((currentForm->prefix & Bits_maxBits64(currentForm->prefixLen)) == 1) {
  131. // Swap 0 and 1 if the prefix is 1, this makes 0001 alias to 1
  132. // because 0 can never show up in the wild, we reuse it for 1.
  133. director = director - (director == 1) + (director == 0);
  134. } else {
  135. // Reuse the number 1 for 2 and 2 for 3 etc. to gain an extra slot in all other forms.
  136. director += (director > 0);
  137. }
  138. if (convertTo == EncodingScheme_convertLabel_convertTo_CANNONICAL) {
  139. // Take into account the fact that if the destination form does not have a 1 prefix,
  140. // an extra number will be available.
  141. int minBitsA = Bits_log2x64(director) + 1;
  142. int minBitsB = Bits_log2x64(director - (director > 0)) + 1;
  143. for (int i = 0; i < scheme->count; i++) {
  144. struct EncodingScheme_Form* form = &scheme->forms[i];
  145. int minBits = ((form->prefix & Bits_maxBits64(form->prefixLen)) == 1)
  146. ? minBitsA : minBitsB;
  147. if (form->bitCount >= minBits) {
  148. convertTo = i;
  149. break;
  150. }
  151. }
  152. }
  153. if (convertTo < 0 || convertTo >= scheme->count) {
  154. // convertTo value is insane
  155. return EncodingScheme_convertLabel_INVALID;
  156. }
  157. struct EncodingScheme_Form* nextForm = &scheme->forms[convertTo];
  158. if (!EncodingScheme_is358(scheme)) {
  159. // don't pull this bug-workaround crap for sane encodings schemes.
  160. } else if ((nextForm->prefix & Bits_maxBits64(nextForm->prefixLen)) == 1) {
  161. // Swap 1 and 0 back if necessary.
  162. director = director - (director == 1) + (director == 0);
  163. } else {
  164. // Or move the numbers down by one.
  165. director -= (director > 0);
  166. }
  167. if ((Bits_log2x64(director) + 1) > nextForm->bitCount) {
  168. // won't fit in requested form
  169. return EncodingScheme_convertLabel_INVALID;
  170. }
  171. if (Bits_log2x64(routeLabel) + EncodingScheme_formSize(nextForm) > 59) {
  172. return EncodingScheme_convertLabel_INVALID;
  173. }
  174. routeLabel <<= nextForm->bitCount;
  175. routeLabel |= director;
  176. routeLabel <<= nextForm->prefixLen;
  177. routeLabel |= nextForm->prefix;
  178. if ((routeLabel & Bits_maxBits64(nextForm->prefixLen + nextForm->bitCount)) == 1) {
  179. // looks like a self-route
  180. return EncodingScheme_convertLabel_INVALID;
  181. }
  182. return routeLabel;
  183. }
  184. /**
  185. * Decode a form from its binary representation.
  186. * Can only use a maximum of 41 bits.
  187. *
  188. * One or more of these binary representation are bitwise concatenated to
  189. * give an unsigned integer; which is encoded in **little endian** to give
  190. * the serialization of Encoding Scheme.
  191. *
  192. * Ten least significant bits of a form are:
  193. *
  194. * 1
  195. * 0 1 2 3 4 5 6 7 0 1
  196. * +-+-+-+-+-+-+-+-+-+-+
  197. * 0 | bitcount| preflen |
  198. * +-+-+-+-+-+-+-+-+-+-+
  199. *
  200. * Previous 'preflen' bits are the prefix
  201. *
  202. * @param out the output which will be populated with the encoding form data.
  203. * @param data the binary data in host order.
  204. * @return the number of bits of data which were consumed by the decoding.
  205. * If the content is definitely not an encoding form, 0 is returned.
  206. */
  207. static inline int decodeForm(struct EncodingScheme_Form* out, uint64_t d)
  208. {
  209. out->prefixLen = d & Bits_maxBits64(5);
  210. d >>= 5;
  211. int bitCount = d & Bits_maxBits64(5);
  212. if (bitCount < 1) {
  213. return 0;
  214. }
  215. out->bitCount = bitCount;
  216. d >>= 5;
  217. out->prefix = d & Bits_maxBits64(out->prefixLen);
  218. return 5 + 5 + out->prefixLen;
  219. }
  220. static inline int encodeForm(struct EncodingScheme_Form* in, uint64_t* data, int bits)
  221. {
  222. *data |= ((uint64_t)in->prefixLen & Bits_maxBits64(5)) << bits;
  223. bits += 5;
  224. *data |= ((uint64_t)in->bitCount & Bits_maxBits64(5)) << bits;
  225. bits += 5;
  226. *data |= ((uint64_t)in->prefix & Bits_maxBits64(in->prefixLen)) << bits;
  227. return 5 + 5 + in->prefixLen;
  228. }
  229. bool EncodingScheme_isSane(struct EncodingScheme* scheme)
  230. {
  231. // Check for obviously insane encoding.
  232. if (scheme->count == 0) {
  233. // No encoding schemes
  234. return false;
  235. }
  236. if (scheme->count > 31) {
  237. // impossible, each form must have a different bitCount and bitCount
  238. // can only be expressed in 5 bits limiting it to 31 bits max and a form
  239. // using zero bits is not allowed so there are only 31 max possibilities.
  240. return false;
  241. }
  242. if (scheme->count == 1) {
  243. // Fixed width encoding, prefix is not allowed and bitcount must be non-zero
  244. if (scheme->forms[0].prefixLen != 0 || scheme->forms[0].prefix != 0) {
  245. // prefixLen must be 0
  246. return false;
  247. }
  248. if (scheme->forms[0].bitCount == 0 || scheme->forms[0].bitCount > 31) {
  249. // bitcount must be non-zero and can't overflow the number
  250. return false;
  251. }
  252. return true;
  253. }
  254. // Variable width encoding.
  255. for (int i = 0; i < scheme->count; i++) {
  256. struct EncodingScheme_Form* form = &scheme->forms[i];
  257. if (form->prefixLen == 0 || form->prefixLen > 31) {
  258. // Prefix must exist in order to distinguish between forms
  259. return false;
  260. }
  261. if (form->bitCount == 0 || form->bitCount > 31) {
  262. // Bitcount must be non-zero
  263. return false;
  264. }
  265. if (EncodingScheme_formSize(form) > 59) {
  266. // cannot be represented in the usable space in a label
  267. return false;
  268. }
  269. if (i > 0 && form->bitCount <= scheme->forms[i-1].bitCount) {
  270. // Forms must be in ascending order.
  271. return false;
  272. }
  273. for (int j = 0; j < scheme->count; j++) {
  274. // Forms must be distinguishable by their prefixes.
  275. if (j != i
  276. && (scheme->forms[j].prefix & Bits_maxBits64(form->prefixLen)) == form->prefix)
  277. {
  278. return false;
  279. }
  280. }
  281. }
  282. return true;
  283. }
  284. List* EncodingScheme_asList(struct EncodingScheme* list, struct Allocator* alloc)
  285. {
  286. Assert_ifParanoid(EncodingScheme_isSane(list));
  287. List* scheme = List_new(alloc);
  288. for (int i = (int)list->count - 1; i >= 0; i--) {
  289. Dict* form = Dict_new(alloc);
  290. Dict_putIntC(form, "prefixLen", list->forms[i].prefixLen, alloc);
  291. Dict_putIntC(form, "bitCount", list->forms[i].bitCount, alloc);
  292. if (list->forms[i].prefixLen == 0) {
  293. Dict_putStringCC(form, "prefix", "", alloc);
  294. } else {
  295. String* pfx = String_newBinary(NULL, 8, alloc);
  296. uint32_t prefix_be = Endian_hostToBigEndian32(list->forms[i].prefix);
  297. Hex_encode(pfx->bytes, 8, (uint8_t*)&prefix_be, 4);
  298. while (pfx->bytes[0] == '0' && pfx->len > 2) {
  299. pfx->bytes += 2;
  300. pfx->len -= 2;
  301. }
  302. Dict_putStringC(form, "prefix", pfx, alloc);
  303. }
  304. List_addDict(scheme, form, alloc);
  305. }
  306. return scheme;
  307. }
  308. struct EncodingScheme* EncodingScheme_fromList(List* scheme, struct Allocator* alloc)
  309. {
  310. struct EncodingScheme* list = Allocator_malloc(alloc, sizeof(struct EncodingScheme));
  311. list->count = List_size(scheme);
  312. list->forms = Allocator_malloc(alloc, sizeof(struct EncodingScheme_Form) * list->count);
  313. for (int i = 0; i < (int)list->count; i++) {
  314. Dict* form = List_getDict(scheme, i);
  315. uint64_t* prefixLen = Dict_getIntC(form, "prefixLen");
  316. uint64_t* bitCount = Dict_getIntC(form, "bitCount");
  317. String* prefixStr = Dict_getStringC(form, "prefix");
  318. if (!prefixLen || !bitCount || !prefixStr || prefixStr->len != 8) {
  319. return NULL;
  320. }
  321. uint32_t prefix_be;
  322. if (Hex_decode((uint8_t*)&prefix_be, 4, prefixStr->bytes, 8) != 4) {
  323. return NULL;
  324. }
  325. list->forms[i].prefixLen = *prefixLen;
  326. list->forms[i].bitCount = *bitCount;
  327. list->forms[i].prefix = Endian_bigEndianToHost32(prefix_be);
  328. }
  329. if (!EncodingScheme_isSane(list)) {
  330. return NULL;
  331. }
  332. return list;
  333. }
  334. String* EncodingScheme_serialize(struct EncodingScheme* list,
  335. struct Allocator* alloc)
  336. {
  337. Assert_ifParanoid(EncodingScheme_isSane(list));
  338. // Create the string as the largest that is possible for the list size.
  339. String* out = String_newBinary(NULL, list->count * 6, alloc);
  340. int bits = 0;
  341. int outIndex = 0;
  342. uint64_t block = 0;
  343. for (int listIndex = 0; listIndex < (int)list->count; listIndex++) {
  344. bits += encodeForm(&list->forms[listIndex], &block, bits);
  345. while (bits > 8) {
  346. Assert_true(outIndex < (int)out->len);
  347. out->bytes[outIndex++] = (uint8_t) (block & 0xff);
  348. bits -= 8;
  349. block >>= 8;
  350. }
  351. }
  352. if (bits > 0) {
  353. out->bytes[outIndex++] = (uint8_t) (block & 0xff);
  354. }
  355. out->len = outIndex;
  356. return out;
  357. }
  358. struct EncodingScheme* EncodingScheme_deserialize(String* data,
  359. struct Allocator* alloc)
  360. {
  361. struct EncodingScheme_Form* forms = NULL;
  362. int outCount = 0;
  363. uint64_t block = 0;
  364. int bits = 0;
  365. int dataIndex = 0;
  366. for (;;) {
  367. // load data into the block from the incoming data source
  368. while (bits < 56 && dataIndex < (int)data->len) {
  369. block |= (((uint64_t)data->bytes[dataIndex++] & 0xff) << bits);
  370. bits += 8;
  371. }
  372. struct EncodingScheme_Form next;
  373. int ret = decodeForm(&next, block);
  374. bits -= ret;
  375. if (!ret || bits < 0) {
  376. if (block || dataIndex < (int)data->len || bits < 0) {
  377. // Invalid encoding
  378. return NULL;
  379. }
  380. break;
  381. }
  382. block >>= ret;
  383. Assert_true((next.prefix >> next.prefixLen) == 0);
  384. outCount += 1;
  385. forms = Allocator_realloc(alloc, forms, outCount * sizeof(struct EncodingScheme_Form));
  386. Bits_memcpy(&forms[outCount-1], &next, sizeof(struct EncodingScheme_Form));
  387. }
  388. struct EncodingScheme* out = Allocator_clone(alloc, (&(struct EncodingScheme) {
  389. .forms = forms,
  390. .count = outCount
  391. }));
  392. return EncodingScheme_isSane(out) ? out : NULL;
  393. }
  394. struct EncodingScheme* EncodingScheme_defineFixedWidthScheme(int bitCount, struct Allocator* alloc)
  395. {
  396. struct NumberCompress_FixedWidthScheme
  397. {
  398. struct EncodingScheme scheme;
  399. struct EncodingScheme_Form form;
  400. };
  401. struct NumberCompress_FixedWidthScheme* out =
  402. Allocator_malloc(alloc, sizeof(struct NumberCompress_FixedWidthScheme));
  403. struct NumberCompress_FixedWidthScheme scheme = {
  404. .scheme = { .count = 1, .forms = &out->form },
  405. .form = { .bitCount = bitCount, .prefixLen = 0, .prefix = 0, },
  406. };
  407. Bits_memcpy(out, &scheme, sizeof(struct NumberCompress_FixedWidthScheme));
  408. Assert_true(EncodingScheme_isSane(&out->scheme));
  409. return &out->scheme;
  410. }
  411. struct EncodingScheme* EncodingScheme_defineDynWidthScheme(struct EncodingScheme_Form* forms,
  412. int formCount,
  413. struct Allocator* alloc)
  414. {
  415. struct EncodingScheme_Form* formsCopy =
  416. Allocator_malloc(alloc, sizeof(struct EncodingScheme_Form) * formCount);
  417. Bits_memcpy(formsCopy, forms, sizeof(struct EncodingScheme_Form) * formCount);
  418. struct EncodingScheme* scheme = Allocator_clone(alloc, (&(struct EncodingScheme) {
  419. .count = formCount,
  420. .forms = formsCopy
  421. }));
  422. Assert_ifParanoid(EncodingScheme_isSane(scheme));
  423. return scheme;
  424. }
  425. int EncodingScheme_compare(struct EncodingScheme* a, struct EncodingScheme* b)
  426. {
  427. if (a->count == b->count) {
  428. return Bits_memcmp(a->forms, b->forms, sizeof(struct EncodingScheme_Form) * a->count);
  429. }
  430. return a->count > b->count ? 1 : -1;
  431. }
  432. /**
  433. * Return true if the route is to the switch's router interface.
  434. */
  435. int EncodingScheme_isSelfRoute(struct EncodingScheme* scheme, uint64_t routeLabel)
  436. {
  437. int formNum = EncodingScheme_getFormNum(scheme, routeLabel);
  438. if (formNum == EncodingScheme_getFormNum_INVALID) {
  439. return 0;
  440. }
  441. struct EncodingScheme_Form* currentForm = &scheme->forms[formNum];
  442. return (routeLabel & Bits_maxBits64(currentForm->prefixLen + currentForm->bitCount)) == 1;
  443. }
  444. int EncodingScheme_isOneHop(struct EncodingScheme* scheme, uint64_t routeLabel)
  445. {
  446. int fn = EncodingScheme_getFormNum(scheme, routeLabel);
  447. if (fn == EncodingScheme_getFormNum_INVALID) { return 0; }
  448. struct EncodingScheme_Form* form = &scheme->forms[fn];
  449. return (Bits_log2x64(routeLabel) == form->prefixLen + form->bitCount);
  450. }