diff options
author | Nikos Mavrogiannopoulos <nmav@gnutls.org> | 2010-09-02 23:10:17 +0200 |
---|---|---|
committer | Nikos Mavrogiannopoulos <nmav@gnutls.org> | 2010-09-02 23:11:42 +0200 |
commit | 5000469e203ada7c65073f32770491057c8233bd (patch) | |
tree | ed82a497f3e772a5844037d5dcba9b36c75176ae | |
parent | 72316eded1cc13dd8a339be92f43eeb79f252193 (diff) | |
download | kernel-crypto-5000469e203ada7c65073f32770491057c8233bd.tar.gz kernel-crypto-5000469e203ada7c65073f32770491057c8233bd.tar.xz kernel-crypto-5000469e203ada7c65073f32770491057c8233bd.zip |
Use the linux kernel heapsort instead of including qsort.
-rw-r--r-- | Makefile | 2 | ||||
-rw-r--r-- | libtomcrypt/headers/tomcrypt.h | 1 | ||||
-rw-r--r-- | libtomcrypt/headers/tomcrypt_cfg.h | 4 | ||||
-rw-r--r-- | libtomcrypt/headers/tomcrypt_custom.h | 2 | ||||
-rw-r--r-- | libtomcrypt/misc/qsort.c | 247 | ||||
-rw-r--r-- | libtommath/tommath.h | 2 |
6 files changed, 6 insertions, 252 deletions
@@ -30,7 +30,7 @@ TOMMATH_OBJECTS = libtommath/bncore.o libtommath/bn_mp_init.o libtommath/bn_mp_c libtommath/bn_mp_to_signed_bin_n.o libtommath/bn_mp_to_unsigned_bin_n.o TOMCRYPT_OBJECTS = libtomcrypt/misc/zeromem.o libtomcrypt/misc/crypt/crypt_argchk.o \ - libtomcrypt/math/rand_prime.o libtomcrypt/misc/qsort.o libtomcrypt/hashes/hash_get_oid.o \ + libtomcrypt/math/rand_prime.o libtomcrypt/hashes/hash_get_oid.o \ libtomcrypt/hashes/crypt_hash_is_valid.o libtomcrypt/hashes/hash_memory.o libtomcrypt/hashes/hash_memory_multi.o \ libtomcrypt/pk/dsa/dsa_make_key.o libtomcrypt/pk/dsa/dsa_export.o libtomcrypt/pk/dsa/dsa_import.o \ libtomcrypt/pk/dsa/dsa_free.o libtomcrypt/pk/dsa/dsa_sign_hash.o libtomcrypt/pk/dsa/dsa_verify_hash.o \ diff --git a/libtomcrypt/headers/tomcrypt.h b/libtomcrypt/headers/tomcrypt.h index fdb6c8d1f16..a9c675d0944 100644 --- a/libtomcrypt/headers/tomcrypt.h +++ b/libtomcrypt/headers/tomcrypt.h @@ -6,6 +6,7 @@ #include <linux/string.h> #include <linux/ctype.h> #include <linux/nls.h> +#include <linux/sort.h> /* use configuration data */ #include <tomcrypt_custom.h> diff --git a/libtomcrypt/headers/tomcrypt_cfg.h b/libtomcrypt/headers/tomcrypt_cfg.h index 8ad90bce4b0..93db10e6729 100644 --- a/libtomcrypt/headers/tomcrypt_cfg.h +++ b/libtomcrypt/headers/tomcrypt_cfg.h @@ -19,11 +19,11 @@ #define LTC_EXPORT #endif -LTC_EXPORT void LTC_CALL XQSORT(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); - /* certain platforms use macros for these, making the prototypes broken */ #ifndef LTC_NO_PROTOTYPES +LTC_EXPORT void LTC_CALL XQSORT(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *)); + /* you can change how memory allocation works ... */ LTC_EXPORT void * LTC_CALL XMALLOC(size_t n); LTC_EXPORT void * LTC_CALL XREALLOC(void *p, size_t n); diff --git a/libtomcrypt/headers/tomcrypt_custom.h b/libtomcrypt/headers/tomcrypt_custom.h index c537dc7605a..76b574487bc 100644 --- a/libtomcrypt/headers/tomcrypt_custom.h +++ b/libtomcrypt/headers/tomcrypt_custom.h @@ -65,7 +65,7 @@ #ifdef qsort #define LTC_NO_PROTOTYPES #endif -#define XQSORT qsort +#define XQSORT(x,y,z,w) sort(x,y,z,w,NULL) #endif /* Easy button? */ diff --git a/libtomcrypt/misc/qsort.c b/libtomcrypt/misc/qsort.c deleted file mode 100644 index 72f51088e35..00000000000 --- a/libtomcrypt/misc/qsort.c +++ /dev/null @@ -1,247 +0,0 @@ -/* Copyright (C) 1991,1992,1996,1997,1999,2004 Free Software Foundation, Inc. - This file is part of the GNU C Library. - Written by Douglas C. Schmidt (schmidt@ics.uci.edu). - - The GNU C Library is free software; you can redistribute it and/or - modify it under the terms of the GNU Lesser General Public - License as published by the Free Software Foundation; either - version 2.1 of the License, or (at your option) any later version. - - The GNU C Library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU - Lesser General Public License for more details. - - You should have received a copy of the GNU Lesser General Public - License along with the GNU C Library; if not, write to the Free - Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA - 02111-1307 USA. */ - -/* If you consider tuning this algorithm, you should consult first: - Engineering a sort function; Jon Bentley and M. Douglas McIlroy; - Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993. */ - -#include <tomcrypt.h> - -/* Byte-wise swap two items of size SIZE. */ -#define SWAP(a, b, size) \ - do \ - { \ - register size_t __size = (size); \ - register char *__a = (a), *__b = (b); \ - do \ - { \ - char __tmp = *__a; \ - *__a++ = *__b; \ - *__b++ = __tmp; \ - } while (--__size > 0); \ - } while (0) - -/* Discontinue quicksort algorithm when partition gets below this size. - This particular magic number was chosen to work best on a Sun 4/260. */ -#define MAX_THRESH 4 - -/* Stack node declarations used to store unfulfilled partition obligations. */ -typedef struct - { - char *lo; - char *hi; - } stack_node; - -/* The next 4 #defines implement a very fast in-line stack abstraction. */ -/* The stack needs log (total_elements) entries (we could even subtract - log(MAX_THRESH)). Since total_elements has type size_t, we get as - upper bound for log (total_elements): - bits per byte (CHAR_BIT) * sizeof(size_t). */ -#define STACK_SIZE (CHAR_BIT * sizeof(size_t)) -#define PUSH(low, high) ((void) ((top->lo = (low)), (top->hi = (high)), ++top)) -#define POP(low, high) ((void) (--top, (low = top->lo), (high = top->hi))) -#define STACK_NOT_EMPTY (stack < top) - - -/* Order size using quicksort. This implementation incorporates - four optimizations discussed in Sedgewick: - - 1. Non-recursive, using an explicit stack of pointer that store the - next array partition to sort. To save time, this maximum amount - of space required to store an array of SIZE_MAX is allocated on the - stack. Assuming a 32-bit (64 bit) integer for size_t, this needs - only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). - Pretty cheap, actually. - - 2. Chose the pivot element using a median-of-three decision tree. - This reduces the probability of selecting a bad pivot value and - eliminates certain extraneous comparisons. - - 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving - insertion sort to order the MAX_THRESH items within each partition. - This is a big win, since insertion sort is faster for small, mostly - sorted array segments. - - 4. The larger of the two sub-partitions is always pushed onto the - stack first, with the algorithm then concentrating on the - smaller partition. This *guarantees* no more than log (total_elems) - stack size is needed (actually O(1) in this case)! */ - -typedef int(*__compar_fn_t)(const void *, const void *); - -void -qsort (void *const pbase, size_t total_elems, size_t size, - __compar_fn_t cmp) -{ - register char *base_ptr = (char *) pbase; - - const size_t max_thresh = MAX_THRESH * size; - - if (total_elems == 0) - /* Avoid lossage with unsigned arithmetic below. */ - return; - - if (total_elems > MAX_THRESH) - { - char *lo = base_ptr; - char *hi = &lo[size * (total_elems - 1)]; - stack_node stack[STACK_SIZE]; - stack_node *top = stack; - - PUSH (NULL, NULL); - - while (STACK_NOT_EMPTY) - { - char *left_ptr; - char *right_ptr; - - /* Select median value from among LO, MID, and HI. Rearrange - LO and HI so the three values are sorted. This lowers the - probability of picking a pathological pivot value and - skips a comparison for both the LEFT_PTR and RIGHT_PTR in - the while loops. */ - - char *mid = lo + size * ((hi - lo) / size >> 1); - - if ((*cmp) ((void *) mid, (void *) lo) < 0) - SWAP (mid, lo, size); - if ((*cmp) ((void *) hi, (void *) mid) < 0) - SWAP (mid, hi, size); - else - goto jump_over; - if ((*cmp) ((void *) mid, (void *) lo) < 0) - SWAP (mid, lo, size); - jump_over:; - - left_ptr = lo + size; - right_ptr = hi - size; - - /* Here's the famous ``collapse the walls'' section of quicksort. - Gotta like those tight inner loops! They are the main reason - that this algorithm runs much faster than others. */ - do - { - while ((*cmp) ((void *) left_ptr, (void *) mid) < 0) - left_ptr += size; - - while ((*cmp) ((void *) mid, (void *) right_ptr) < 0) - right_ptr -= size; - - if (left_ptr < right_ptr) - { - SWAP (left_ptr, right_ptr, size); - if (mid == left_ptr) - mid = right_ptr; - else if (mid == right_ptr) - mid = left_ptr; - left_ptr += size; - right_ptr -= size; - } - else if (left_ptr == right_ptr) - { - left_ptr += size; - right_ptr -= size; - break; - } - } - while (left_ptr <= right_ptr); - - /* Set up pointers for next iteration. First determine whether - left and right partitions are below the threshold size. If so, - ignore one or both. Otherwise, push the larger partition's - bounds on the stack and continue sorting the smaller one. */ - - if ((size_t) (right_ptr - lo) <= max_thresh) - { - if ((size_t) (hi - left_ptr) <= max_thresh) - /* Ignore both small partitions. */ - POP (lo, hi); - else - /* Ignore small left partition. */ - lo = left_ptr; - } - else if ((size_t) (hi - left_ptr) <= max_thresh) - /* Ignore small right partition. */ - hi = right_ptr; - else if ((right_ptr - lo) > (hi - left_ptr)) - { - /* Push larger left partition indices. */ - PUSH (lo, right_ptr); - lo = left_ptr; - } - else - { - /* Push larger right partition indices. */ - PUSH (left_ptr, hi); - hi = right_ptr; - } - } - } - - /* Once the BASE_PTR array is partially sorted by quicksort the rest - is completely sorted using insertion sort, since this is efficient - for partitions below MAX_THRESH size. BASE_PTR points to the beginning - of the array to sort, and END_PTR points at the very last element in - the array (*not* one beyond it!). */ - - { - char *const end_ptr = &base_ptr[size * (total_elems - 1)]; - char *tmp_ptr = base_ptr; - char *thresh = min(end_ptr, base_ptr + max_thresh); - register char *run_ptr; - - /* Find smallest element in first threshold and place it at the - array's beginning. This is the smallest array element, - and the operation speeds up insertion sort's inner loop. */ - - for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size) - if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0) - tmp_ptr = run_ptr; - - if (tmp_ptr != base_ptr) - SWAP (tmp_ptr, base_ptr, size); - - /* Insertion sort, running from left-hand-side up to right-hand-side. */ - - run_ptr = base_ptr + size; - while ((run_ptr += size) <= end_ptr) - { - tmp_ptr = run_ptr - size; - while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr) < 0) - tmp_ptr -= size; - - tmp_ptr += size; - if (tmp_ptr != run_ptr) - { - char *trav; - - trav = run_ptr + size; - while (--trav >= run_ptr) - { - char c = *trav; - char *hi, *lo; - - for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo) - *hi = *lo; - *hi = c; - } - } - } - } -} diff --git a/libtommath/tommath.h b/libtommath/tommath.h index 31ded829977..491bcc2221a 100644 --- a/libtommath/tommath.h +++ b/libtommath/tommath.h @@ -71,7 +71,7 @@ extern "C" { # define DIGIT_BIT 15 #elif BITS_PER_LONG == 64 - + typedef uint32_t mp_digit; typedef uint64_t mp_word; # define DIGIT_BIT 31 |