pintos-os.org Git - openvswitch/blob - tests/test-csum.c

   1 /*
   2  * Copyright (c) 2009, 2010 Nicira Networks.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at:
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <config.h>
  18 #include "csum.h"
  19 #include <inttypes.h>
  20 #include <netinet/in.h>
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <string.h>
  24 #include "random.h"
  25 #include "unaligned.h"
  26 #include "util.h"
  27
  28 #undef NDEBUG
  29 #include <assert.h>
  30
  31 struct test_case {
  32     char *data;
  33     size_t size;                /* Test requires a multiple of 4. */
  34     uint16_t csum;
  35 };
  36
  37 #define TEST_CASE(DATA, CSUM) { DATA, (sizeof DATA) - 1, CSUM }
  38
  39 static const struct test_case test_cases[] = {
  40     /* RFC 1071 section 3. */
  41     TEST_CASE("\x00\x01\xf2\x03"
  42               "\xf4\xf5\xf6\xf7",
  43               (uint16_t) ~0xddf2),
  44
  45     /* http://www.sbprojects.com/projects/tcpip/theory/theory14.htm */
  46     TEST_CASE("\x45\x00\x00\x28"
  47               "\x1F\xFD\x40\x00"
  48               "\x80\x06\x00\x00"
  49               "\xC0\xA8\x3B\x0A"
  50               "\xC0\xA8\x3B\x32",
  51               0xe345),
  52
  53     /* http://mathforum.org/library/drmath/view/54379.html */
  54     TEST_CASE("\x86\x5e\xac\x60"
  55               "\x71\x2a\x81\xb5",
  56               0xda60),
  57 };
  58
  59 static void
  60 mark(char c)
  61 {
  62     putchar(c);
  63     fflush(stdout);
  64 }
  65
  66 #if 0
  67 /* This code is useful for generating new test cases for RFC 1624 section 4. */
  68 static void
  69 generate_rfc1624_test_case(void)
  70 {
  71     int i;
  72
  73     for (i = 0; i < 10000000; i++) {
  74         uint32_t data[8];
  75         int j;
  76
  77         for (j = 0; j < 8; j++) {
  78             data[j] = random_uint32();
  79         }
  80         data[7] &= 0x0000ffff;
  81         data[7] |= 0x55550000;
  82         if (ntohs(~csum(data, sizeof data - 2)) == 0xcd7a) {
  83             ovs_hex_dump(stdout, data, sizeof data, 0, false);
  84             exit(0);
  85         }
  86     }
  87 }
  88 #endif
  89
  90
  91
  92 /* Make sure we get the calculation in RFC 1624 section 4 correct. */
  93 static void
  94 test_rfc1624(void)
  95 {
  96     /* "...an IP packet header in which a 16-bit field m = 0x5555..." */
  97     uint8_t data[32] =
  98         "\xfe\x8f\xc1\x14\x4b\x6f\x70\x2a\x80\x29\x78\xc0\x58\x81\x77\xaa"
  99         "\x66\x64\xfc\x96\x63\x97\x64\xee\x12\x53\x1d\xa9\x2d\xa9\x55\x55";
 100
 101     /* "...the one's complement sum of all other header octets is 0xCD7A." */
 102     assert(ntohs(csum(data, sizeof data - 2)) == (uint16_t) ~0xcd7a);
 103
 104     /* "...the header checksum would be:
 105
 106           HC = ~(0xCD7A + 0x5555)
 107              = ~0x22D0
 108              =  0xDD2F"
 109     */
 110     assert(ntohs(csum(data, sizeof data)) == 0xdd2f);
 111
 112     /* "a 16-bit field m = 0x5555 changes to m' = 0x3285..." */
 113     data[30] = 0x32;
 114     data[31] = 0x85;
 115
 116     /* "The new checksum via recomputation is:
 117
 118           HC' = ~(0xCD7A + 0x3285)
 119               = ~0xFFFF
 120               =  0x0000"
 121     */
 122     assert(ntohs(csum(data, sizeof data)) == 0x0000);
 123
 124     /* "Applying [Eqn. 3] to the example above, we get the correct result:
 125
 126           HC' = ~(C + (-m) + m')
 127               = ~(0x22D0 + ~0x5555 + 0x3285)
 128               = ~0xFFFF
 129               =  0x0000" */
 130     assert(recalc_csum16(0xdd2f, 0x5555, 0x3285) == 0x0000);
 131
 132     mark('#');
 133 }
 134
 135 int
 136 main(void)
 137 {
 138     const struct test_case *tc;
 139     int i;
 140
 141     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 142         const uint16_t *data16 = (const uint16_t *) tc->data;
 143         const uint32_t *data32 = (const uint32_t *) tc->data;
 144         uint32_t partial;
 145
 146         /* Test csum(). */
 147         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 148         mark('.');
 149
 150         /* Test csum_add16(). */
 151         partial = 0;
 152         for (i = 0; i < tc->size / 2; i++) {
 153             partial = csum_add16(partial, get_unaligned_u16(&data16[i]));
 154         }
 155         assert(ntohs(csum_finish(partial)) == tc->csum);
 156         mark('.');
 157
 158         /* Test csum_add32(). */
 159         partial = 0;
 160         for (i = 0; i < tc->size / 4; i++) {
 161             partial = csum_add32(partial, get_unaligned_u32(&data32[i]));
 162         }
 163         assert(ntohs(csum_finish(partial)) == tc->csum);
 164         mark('.');
 165
 166         /* Test alternating csum_add16() and csum_add32(). */
 167         partial = 0;
 168         for (i = 0; i < tc->size / 4; i++) {
 169             if (i % 2) {
 170                 partial = csum_add32(partial, get_unaligned_u32(&data32[i]));
 171             } else {
 172                 uint16_t u0 = get_unaligned_u16(&data16[i * 2]);
 173                 uint16_t u1 = get_unaligned_u16(&data16[i * 2 + 1]);
 174                 partial = csum_add16(partial, u0);
 175                 partial = csum_add16(partial, u1);
 176             }
 177         }
 178         assert(ntohs(csum_finish(partial)) == tc->csum);
 179         mark('.');
 180
 181         /* Test csum_continue(). */
 182         partial = 0;
 183         for (i = 0; i < tc->size / 4; i++) {
 184             if (i) {
 185                 partial = csum_continue(partial, &data32[i], 4);
 186             } else {
 187                 partial = csum_continue(partial, &data16[i * 2], 2);
 188                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 189             }
 190         }
 191         assert(ntohs(csum_finish(partial)) == tc->csum);
 192         mark('#');
 193     }
 194
 195     test_rfc1624();
 196
 197     /* Test recalc_csum16(). */
 198     for (i = 0; i < 32; i++) {
 199         uint16_t old_u16, new_u16;
 200         uint16_t old_csum;
 201         uint16_t data[16];
 202         int j, index;
 203
 204         for (j = 0; j < ARRAY_SIZE(data); j++) {
 205             data[j] = random_uint32();
 206         }
 207         old_csum = csum(data, sizeof data);
 208         index = random_range(ARRAY_SIZE(data));
 209         old_u16 = data[index];
 210         new_u16 = data[index] = random_uint32();
 211         assert(csum(data, sizeof data)
 212                == recalc_csum16(old_csum, old_u16, new_u16));
 213         mark('.');
 214     }
 215     mark('#');
 216
 217     /* Test recalc_csum32(). */
 218     for (i = 0; i < 32; i++) {
 219         uint32_t old_u32, new_u32;
 220         uint16_t old_csum;
 221         uint32_t data[16];
 222         int j, index;
 223
 224         for (j = 0; j < ARRAY_SIZE(data); j++) {
 225             data[j] = random_uint32();
 226         }
 227         old_csum = csum(data, sizeof data);
 228         index = random_range(ARRAY_SIZE(data));
 229         old_u32 = data[index];
 230         new_u32 = data[index] = random_uint32();
 231         assert(csum(data, sizeof data)
 232                == recalc_csum32(old_csum, old_u32, new_u32));
 233         mark('.');
 234     }
 235     mark('#');
 236
 237     putchar('\n');
 238
 239     return 0;
 240 }