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

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