Back to index

tor  0.2.3.19-rc
di_ops.c
Go to the documentation of this file.
00001 /* Copyright (c) 2011-2012, The Tor Project, Inc. */
00002 /* See LICENSE for licensing information */
00003 
00009 #include "orconfig.h"
00010 #include "di_ops.h"
00011 
00023 int
00024 tor_memcmp(const void *a, const void *b, size_t len)
00025 {
00026   const uint8_t *x = a;
00027   const uint8_t *y = b;
00028   size_t i = len;
00029   int retval = 0;
00030 
00031   /* This loop goes from the end of the arrays to the start.  At the
00032    * start of every iteration, before we decrement i, we have set
00033    * "retval" equal to the result of memcmp(a+i,b+i,len-i).  During the
00034    * loop, we update retval by leaving it unchanged if x[i]==y[i] and
00035    * setting it to x[i]-y[i] if x[i]!= y[i].
00036    *
00037    * The following assumes we are on a system with two's-complement
00038    * arithmetic.  We check for this at configure-time with the check
00039    * that sets USING_TWOS_COMPLEMENT.  If we aren't two's complement, then
00040    * torint.h will stop compilation with an error.
00041    */
00042   while (i--) {
00043     int v1 = x[i];
00044     int v2 = y[i];
00045     int equal_p = v1 ^ v2;
00046 
00047     /* The following sets bits 8 and above of equal_p to 'equal_p ==
00048      * 0', and thus to v1 == v2.  (To see this, note that if v1 ==
00049      * v2, then v1^v2 == equal_p == 0, so equal_p-1 == -1, which is the
00050      * same as ~0 on a two's-complement machine.  Then note that if
00051      * v1 != v2, then 0 < v1 ^ v2 < 256, so 0 <= equal_p - 1 < 255.)
00052      */
00053     --equal_p;
00054 
00055     equal_p >>= 8;
00056     /* Thanks to (sign-preserving) arithmetic shift, equal_p is now
00057      * equal to -(v1 == v2), which is exactly what we need below.
00058      * (Since we're assuming two's-complement arithmetic, -1 is the
00059      * same as ~0 (all bits set).)
00060      *
00061      * (The result of an arithmetic shift on a negative value is
00062      * actually implementation-defined in standard C.  So how do we
00063      * get away with assuming it?  Easy.  We check.) */
00064 #if ((-60 >> 8) != -1)
00065 #error "According to cpp, right-shift doesn't perform sign-extension."
00066 #endif
00067 #ifndef RSHIFT_DOES_SIGN_EXTEND
00068 #error "According to configure, right-shift doesn't perform sign-extension."
00069 #endif
00070 
00071     /* If v1 == v2, equal_p is ~0, so this will leave retval
00072      * unchanged; otherwise, equal_p is 0, so this will zero it. */
00073     retval &= equal_p;
00074 
00075     /* If v1 == v2, then this adds 0, and leaves retval unchanged.
00076      * Otherwise, we just zeroed retval, so this sets it to v1 - v2. */
00077     retval += (v1 - v2);
00078 
00079     /* There.  Now retval is equal to its previous value if v1 == v2, and
00080      * equal to v1 - v2 if v1 != v2. */
00081   }
00082 
00083   return retval;
00084 }
00085 
00095 int
00096 tor_memeq(const void *a, const void *b, size_t sz)
00097 {
00098   /* Treat a and b as byte ranges. */
00099   const uint8_t *ba = a, *bb = b;
00100   uint32_t any_difference = 0;
00101   while (sz--) {
00102     /* Set byte_diff to all of those bits that are different in *ba and *bb,
00103      * and advance both ba and bb. */
00104     const uint8_t byte_diff = *ba++ ^ *bb++;
00105 
00106     /* Set bits in any_difference if they are set in byte_diff. */
00107     any_difference |= byte_diff;
00108   }
00109 
00110   /* Now any_difference is 0 if there are no bits different between
00111    * a and b, and is nonzero if there are bits different between a
00112    * and b.  Now for paranoia's sake, let's convert it to 0 or 1.
00113    *
00114    * (If we say "!any_difference", the compiler might get smart enough
00115    * to optimize-out our data-independence stuff above.)
00116    *
00117    * To unpack:
00118    *
00119    * If any_difference == 0:
00120    *            any_difference - 1 == ~0
00121    *     (any_difference - 1) >> 8 == 0x00ffffff
00122    *     1 & ((any_difference - 1) >> 8) == 1
00123    *
00124    * If any_difference != 0:
00125    *            0 < any_difference < 256, so
00126    *            0 < any_difference - 1 < 255
00127    *            (any_difference - 1) >> 8 == 0
00128    *            1 & ((any_difference - 1) >> 8) == 0
00129    */
00130 
00131   return 1 & ((any_difference - 1) >> 8);
00132 }
00133