1
0

EncodingScheme.c 15 KB

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