Even if you inline your code, (previous examples) I don't think any of the
functions presented is faster than memcmp() from the standard C library.
Earlier email I presented a challenge for searching a table containing a large
number of strings. I indicated that class of problem brings about its own
method of solution.
I have used may tricks to speed up string matching, including the use of
hashing. This subject and example can be handled off line.
Regards
Leslie
Mr. Leslie Satenstein
Montréal Québec, Canada
From: Joel Rees <[email protected]>
To: "[email protected]" <[email protected]>
Sent: Thursday, October 30, 2014 11:38 AM
Subject: Re: streql - Constant-time string comparison
Here's the result of my work to this point:
---------------------------
/* Near-constant run time string/memory compare, with test frame.
** by Joel Rees,
** derived from work by Peter Scott, Riley Baird, et. al., see
** https://lists.debian.org/debian-security/2014/10/msg00060.html
** https://github.com/PeterScott/streql
**
** Use allowed under GPL v. 3, see
** http://www.gnu.org/copyleft/gpl.html
*/
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
/* dbg */ static int gcount = 0;
// The core function: test two regions of memory for bytewise equality
with constant time.
// If cmplength is less than min( xlen, ylen ), comparison is incomplete.
// Lengths should be signed to make conditionals more balanced.
static int equals_internal_constime(
const char *x, int xlen,
const char *y, int ylen,
int cmplength) {
int result = 0;
while ( --cmplength >= 0 ) {
char xtemp;
char ytemp;
/* Using unsigned lengths here would induce unbalanced conditionals:
** unsigned int xlen;
** if ( xlen > 0 ) {
** xtemp = *x++;
** --xlen;
** }
** else {
** xtemp = 0;
** }
** While this might be a problem with 16 bit ints,
** you really aren't going to be comparing strings > 2^31 bytes
with this function.
*/
xtemp = ( --xlen >= 0 ) ? *x++ : 0;
ytemp = ( --ylen >= 0 ) ? *y++ : 0;
/* dbg */ ++gcount;
result |= xtemp ^ ytemp;
/* dbg printf( "%c(%d):%c(%d) =>%d@%d\n", xtemp, xlen, ytemp, ylen,
result, gcount ); */
}
return (xlen == ylen) && (result == 0);
}
int main( int argc, char * argv[] ) {
char * left, * right;
int max = 32;
int result = 0;
if ( argc > 2 ) {
left = argv[ 1 ];
right = argv[ 2 ];
if ( argc > 3 ) max = strtol( argv[ 3 ], NULL, 0 );
gcount = 0;
result = equals_internal_constime( left, strlen( left ), right,
strlen( right ), max );
printf( "result: %d, strcmp: %d, count: %d\n", result, strcmp(
left, right ), gcount );
if ( result != ( strcmp( left, right ) == 0 ) ) {
fputs( "*** failed ***\n", stdout );
}
}
return EXIT_SUCCESS;
}
---------------------------
Note the change to signed lengths and the reasoning.
--
Joel Rees
--
To UNSUBSCRIBE, email to [email protected]
with a subject of "unsubscribe". Trouble? Contact [email protected]
Archive:
https://lists.debian.org/CAAr43iNAJu-tMpvJ3nh4HTPJK=dy1td0gp-cyzza9de49fe...@mail.gmail.com
