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

   1 /*
   2  * Copyright (c) 2009, 2010, 2011 Nicira, Inc.
   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               0xffff - 0xddf2 /* ~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)) == 0xffff - 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(htons(0xdd2f), htons(0x5555), htons(0x3285))
 131            == htons(0x0000));
 132
 133     mark('#');
 134 }
 135
 136 int
 137 main(void)
 138 {
 139     const struct test_case *tc;
 140     int i;
 141
 142     for (tc = test_cases; tc < &test_cases[ARRAY_SIZE(test_cases)]; tc++) {
 143         const void *data = tc->data;
 144         const ovs_be16 *data16 = (OVS_FORCE const ovs_be16 *) data;
 145         const ovs_be32 *data32 = (OVS_FORCE const ovs_be32 *) data;
 146         uint32_t partial;
 147
 148         /* Test csum(). */
 149         assert(ntohs(csum(tc->data, tc->size)) == tc->csum);
 150         mark('.');
 151
 152         /* Test csum_add16(). */
 153         partial = 0;
 154         for (i = 0; i < tc->size / 2; i++) {
 155             partial = csum_add16(partial, get_unaligned_be16(&data16[i]));
 156         }
 157         assert(ntohs(csum_finish(partial)) == tc->csum);
 158         mark('.');
 159
 160         /* Test csum_add32(). */
 161         partial = 0;
 162         for (i = 0; i < tc->size / 4; i++) {
 163             partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 164         }
 165         assert(ntohs(csum_finish(partial)) == tc->csum);
 166         mark('.');
 167
 168         /* Test alternating csum_add16() and csum_add32(). */
 169         partial = 0;
 170         for (i = 0; i < tc->size / 4; i++) {
 171             if (i % 2) {
 172                 partial = csum_add32(partial, get_unaligned_be32(&data32[i]));
 173             } else {
 174                 ovs_be16 u0 = get_unaligned_be16(&data16[i * 2]);
 175                 ovs_be16 u1 = get_unaligned_be16(&data16[i * 2 + 1]);
 176                 partial = csum_add16(partial, u0);
 177                 partial = csum_add16(partial, u1);
 178             }
 179         }
 180         assert(ntohs(csum_finish(partial)) == tc->csum);
 181         mark('.');
 182
 183         /* Test csum_continue(). */
 184         partial = 0;
 185         for (i = 0; i < tc->size / 4; i++) {
 186             if (i) {
 187                 partial = csum_continue(partial, &data32[i], 4);
 188             } else {
 189                 partial = csum_continue(partial, &data16[i * 2], 2);
 190                 partial = csum_continue(partial, &data16[i * 2 + 1], 2);
 191             }
 192         }
 193         assert(ntohs(csum_finish(partial)) == tc->csum);
 194         mark('#');
 195     }
 196
 197     test_rfc1624();
 198
 199     /* Test recalc_csum16(). */
 200     for (i = 0; i < 32; i++) {
 201         ovs_be16 old_u16, new_u16;
 202         ovs_be16 old_csum;
 203         ovs_be16 data[16];
 204         int j, index;
 205
 206         for (j = 0; j < ARRAY_SIZE(data); j++) {
 207             data[j] = (OVS_FORCE ovs_be16) random_uint32();
 208         }
 209         old_csum = csum(data, sizeof data);
 210         index = random_range(ARRAY_SIZE(data));
 211         old_u16 = data[index];
 212         new_u16 = data[index] = (OVS_FORCE ovs_be16) random_uint32();
 213         assert(csum(data, sizeof data)
 214                == recalc_csum16(old_csum, old_u16, new_u16));
 215         mark('.');
 216     }
 217     mark('#');
 218
 219     /* Test recalc_csum32(). */
 220     for (i = 0; i < 32; i++) {
 221         ovs_be32 old_u32, new_u32;
 222         ovs_be16 old_csum;
 223         ovs_be32 data[16];
 224         int j, index;
 225
 226         for (j = 0; j < ARRAY_SIZE(data); j++) {
 227             data[j] = (OVS_FORCE ovs_be32) random_uint32();
 228         }
 229         old_csum = csum(data, sizeof data);
 230         index = random_range(ARRAY_SIZE(data));
 231         old_u32 = data[index];
 232         new_u32 = data[index] = (OVS_FORCE ovs_be32) random_uint32();
 233         assert(csum(data, sizeof data)
 234                == recalc_csum32(old_csum, old_u32, new_u32));
 235         mark('.');
 236     }
 237     mark('#');
 238
 239     putchar('\n');
 240
 241     return 0;
 242 }