1386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 2386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx.c 3386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 4386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * a replay database with extended range, using a rollover counter 5386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 6386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * David A. McGrew 7386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Cisco Systems, Inc. 8386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 9386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 10386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 11386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 12386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Copyright (c) 2001-2006, Cisco Systems, Inc. 13386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * All rights reserved. 14386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 15386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistribution and use in source and binary forms, with or without 16386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * modification, are permitted provided that the following conditions 17386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * are met: 18386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 19386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistributions of source code must retain the above copyright 20386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * notice, this list of conditions and the following disclaimer. 21386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 22386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistributions in binary form must reproduce the above 23386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * copyright notice, this list of conditions and the following 24386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * disclaimer in the documentation and/or other materials provided 25386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * with the distribution. 26386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 27386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Neither the name of the Cisco Systems, Inc. nor the names of its 28386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * contributors may be used to endorse or promote products derived 29386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * from this software without specific prior written permission. 30386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 31386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 34386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 35386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 36386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 37386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 38386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 39386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 41386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 42386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * OF THE POSSIBILITY OF SUCH DAMAGE. 43386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 44386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 45386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 46386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "rdbx.h" 47386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 48386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 49386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 50386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * from draft-ietf-avt-srtp-00.txt: 51386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 52386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * A receiver reconstructs the index i of a packet with sequence 53386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * number s using the estimate 54386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 55386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * i = 65,536 * t + s, 56386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 57386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * where t is chosen from the set { r-1, r, r+1 } such that i is 58386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * closest to the value 65,536 * r + s_l. If the value r+1 is used, 59386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * then the rollover counter r in the cryptographic context is 60386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * incremented by one (if the packet containing s is authentic). 61386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 62386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 63386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 64386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 65386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 66386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx implementation notes 67386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 68386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * A xtd_seq_num_t is essentially a sequence number for which some of 69386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * the data on the wire are implicit. It logically consists of a 70386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rollover counter and a sequence number; the sequence number is the 71386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * explicit part, and the rollover counter is the implicit part. 72386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 73386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Upon receiving a sequence_number (e.g. in a newly received SRTP 74386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * packet), the complete xtd_seq_num_t can be estimated by using a 75386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * local xtd_seq_num_t as a basis. This is done using the function 76386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * index_guess(&local, &guess, seq_from_packet). This function 77386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * returns the difference of the guess and the local value. The local 78386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * xtd_seq_num_t can be moved forward to the guess using the function 79386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * index_advance(&guess, delta), where delta is the difference. 80386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 81386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 82386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * A rdbx_t consists of a xtd_seq_num_t and a bitmask. The index is highest 83386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * sequence number that has been received, and the bitmask indicates 84386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * which of the recent indicies have been received as well. The 85386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * highest bit in the bitmask corresponds to the index in the bitmask. 86386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 87386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 88386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 89386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarivoid 90386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariindex_init(xtd_seq_num_t *pi) { 91386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 92386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *pi = make64(0,0); 93386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 94386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *pi = 0; 95386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 96386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 97386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 98386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarivoid 99386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariindex_advance(xtd_seq_num_t *pi, sequence_number_t s) { 100386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 101386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* a > ~b means a+b will generate a carry */ 102386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* s is uint16 here */ 103386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *pi = make64(high32(*pi) + (s > ~low32(*pi) ? 1 : 0),low32(*pi) + s); 104386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 105386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *pi += s; 106386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 107386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 108386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 109386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 110386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 111386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * index_guess(local, guess, s) 112386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 113386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * given a xtd_seq_num_t local (which represents the last 114386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * known-to-be-good received xtd_seq_num_t) and a sequence number s 115386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * (from a newly arrived packet), sets the contents of *guess to 116386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * contain the best guess of the packet index to which s corresponds, 117386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * and returns the difference between *guess and *local 118386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 119386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * nota bene - the output is a signed integer, DON'T cast it to a 120386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * unsigned integer! 121386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 122386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 123386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariint 124386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariindex_guess(const xtd_seq_num_t *local, 125386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari xtd_seq_num_t *guess, 126386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari sequence_number_t s) { 127386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 128386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint32_t local_roc = ((high32(*local) << 16) | 129386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari (low32(*local) >> 16)); 130386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint16_t local_seq = (uint16_t) (low32(*local)); 131386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 132386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint32_t local_roc = (uint32_t)(*local >> 16); 133386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint16_t local_seq = (uint16_t) *local; 134386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 135386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 136386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint32_t guess_roc = ((high32(*guess) << 16) | 137386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari (low32(*guess) >> 16)); 138386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint16_t guess_seq = (uint16_t) (low32(*guess)); 139386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 140386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint32_t guess_roc = (uint32_t)(*guess >> 16); 141386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint16_t guess_seq = (uint16_t) *guess; 142386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 143386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari int difference; 144386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 145386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (local_seq < seq_num_median) { 146386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (s - local_seq > seq_num_median) { 147386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari guess_roc = local_roc - 1; 148386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // The return value is the relative difference from local_seq to s. 149386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // The original value is negation of its purpose. According to document 150386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // http://www.ietf.org/rfc/rfc3711.txt, when this condition is true, the 151386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // resulting new index should be (local_roc-1, s). But original logic 152386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // will end up positive difference and rdbx_check would pass. Hence after 153386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // rdbx_add_index would make local index to be the wrong value because 154386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // local index should not be updated in this case. For example, when 155386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // local index is (1, 100) and next sequence is 65530, the wrong updated 156386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari // index would be (1, 205). 157386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari difference = s - local_seq - seq_num_max; 158386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else { 159386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari guess_roc = local_roc; 160386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari difference = s - local_seq; 161386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 162386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else { 163386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (local_seq - seq_num_median > s) { 164386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari guess_roc = local_roc+1; 165386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari difference = seq_num_max - local_seq + s; 166386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else { 167386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari difference = s - local_seq; 168386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari guess_roc = local_roc; 169386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 170386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 171386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari guess_seq = s; 172386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 173386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* Note: guess_roc is 32 bits, so this generates a 48-bit result! */ 174386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 175386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *guess = make64(guess_roc >> 16, 176386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari (guess_roc << 16) | guess_seq); 177386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 178386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *guess = (((uint64_t) guess_roc) << 16) | guess_seq; 179386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 180386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 181386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return difference; 182386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 183386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 184386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 185386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx 186386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 187386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 188386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 189386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 190386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 191386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_init(&r, ws) initializes the rdbx_t pointed to by r with window size ws 192386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 193386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 194386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 195386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_init(rdbx_t *rdbx, unsigned long ws) { 196386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (ws == 0) 197386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_bad_param; 198386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 199386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (bitvector_alloc(&rdbx->bitmask, ws) != 0) 200386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_alloc_fail; 201386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 202386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari index_init(&rdbx->index); 203386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 204386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 205386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 206386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 207386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 208386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_uninit(&r) uninitializes the rdbx_t pointed to by r 209386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 210386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 211386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 212386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_uninit(rdbx_t *rdbx) { 213386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari bitvector_dealloc(&rdbx->bitmask); 214386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 215386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 216386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 217386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 218386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 219386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_set_roc(rdbx, roc) initalizes the rdbx_t at the location rdbx 220386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * to have the rollover counter value roc. If that value is less than 221386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * the current rollover counter value, then the function returns 222386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * err_status_replay_old; otherwise, err_status_ok is returned. 223386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 224386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 225386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 226386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 227386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_set_roc(rdbx_t *rdbx, uint32_t roc) { 228386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari bitvector_set_to_zero(&rdbx->bitmask); 229386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 230386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 231386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari #error not yet implemented 232386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 233386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 234386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* make sure that we're not moving backwards */ 235386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (roc < (rdbx->index >> 16)) 236386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_replay_old; 237386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 238386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdbx->index &= 0xffff; /* retain lowest 16 bits */ 239386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdbx->index |= ((uint64_t)roc) << 16; /* set ROC */ 240386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 241386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 242386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 243386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 244386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 245386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 246386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_get_packet_index(rdbx) returns the value of the packet index 247386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * for the rdbx_t pointed to by rdbx 248386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 249386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 250386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 251386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarixtd_seq_num_t 252386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_get_packet_index(const rdbx_t *rdbx) { 253386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return rdbx->index; 254386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 255386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 256386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 257386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_get_window_size(rdbx) returns the value of the window size 258386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * for the rdbx_t pointed to by rdbx 259386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 260386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 261386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 262386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariunsigned long 263386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_get_window_size(const rdbx_t *rdbx) { 264386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return bitvector_get_length(&rdbx->bitmask); 265386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 266386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 267386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 268386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_check(&r, delta) checks to see if the xtd_seq_num_t 269386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * which is at rdbx->index + delta is in the rdb 270386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 271386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 272386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 273386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_check(const rdbx_t *rdbx, int delta) { 274386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 275386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (delta > 0) { /* if delta is positive, it's good */ 276386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 277386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else if ((int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta < 0) { 278386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* if delta is lower than the bitmask, it's bad */ 279386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_replay_old; 280386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else if (bitvector_get_bit(&rdbx->bitmask, 281386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari (int)(bitvector_get_length(&rdbx->bitmask) - 1) + delta) == 1) { 282386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* delta is within the window, so check the bitmask */ 283386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_replay_fail; 284386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 285386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* otherwise, the index is okay */ 286386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 287386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 288386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 289386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 290386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 291386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_add_index adds the xtd_seq_num_t at rdbx->window_start + d to 292386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * replay_db (and does *not* check if that xtd_seq_num_t appears in db) 293386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 294386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * this function should be called only after replay_check has 295386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * indicated that the index does not appear in the rdbx, e.g., a mutex 296386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * should protect the rdbx between these calls if need be 297386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 298386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 299386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 300386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_add_index(rdbx_t *rdbx, int delta) { 301386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 302386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (delta > 0) { 303386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* shift forward by delta */ 304386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari index_advance(&rdbx->index, delta); 305386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari bitvector_left_shift(&rdbx->bitmask, delta); 306386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari bitvector_set_bit(&rdbx->bitmask, bitvector_get_length(&rdbx->bitmask) - 1); 307386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } else { 308386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* delta is in window, so flip bit in bitmask */ 309386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari bitvector_set_bit(&rdbx->bitmask, -delta); 310386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 311386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 312386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* note that we need not consider the case that delta == 0 */ 313386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 314386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 315386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 316386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 317386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 318386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 319386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 320386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * rdbx_estimate_index(rdbx, guess, s) 321386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 322386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * given an rdbx and a sequence number s (from a newly arrived packet), 323386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * sets the contents of *guess to contain the best guess of the packet 324386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * index to which s corresponds, and returns the difference between 325386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * *guess and the locally stored synch info 326386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 327386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 328386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariint 329386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdbx_estimate_index(const rdbx_t *rdbx, 330386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari xtd_seq_num_t *guess, 331386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari sequence_number_t s) { 332386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 333386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* 334386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * if the sequence number and rollover counter in the rdbx are 335386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * non-zero, then use the index_guess(...) function, otherwise, just 336386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * set the rollover counter to zero (since the index_guess(...) 337386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * function might incorrectly guess that the rollover counter is 338386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 0xffffffff) 339386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 340386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 341386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 342386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* seq_num_median = 0x8000 */ 343386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (high32(rdbx->index) > 0 || 344386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari low32(rdbx->index) > seq_num_median) 345386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 346386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdbx->index > seq_num_median) 347386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 348386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return index_guess(&rdbx->index, guess, s); 349386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 350386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 351386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *guess = make64(0,(uint32_t) s); 352386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 353386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari *guess = s; 354386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 355386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 356386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#ifdef NO_64BIT_MATH 357386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return s - (uint16_t) low32(rdbx->index); 358386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#else 359386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return s - (uint16_t) rdbx->index; 360386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#endif 361386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 362