| 1 | /* |
1 | /* |
| 2 | * Copyright (c) 2000-2003 Marc Alexander Lehmann <pcg@goof.com> |
2 | * Copyright (c) 2000-2005 Marc Alexander Lehmann <schmorp@schmorp.de> |
| 3 | * |
3 | * |
| 4 | * Redistribution and use in source and binary forms, with or without modifica- |
4 | * Redistribution and use in source and binary forms, with or without modifica- |
| 5 | * tion, are permitted provided that the following conditions are met: |
5 | * tion, are permitted provided that the following conditions are met: |
| 6 | * |
6 | * |
| 7 | * 1. Redistributions of source code must retain the above copyright notice, |
7 | * 1. Redistributions of source code must retain the above copyright notice, |
| … | |
… | |
| 22 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; |
22 | * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; |
| 23 | * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, |
23 | * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, |
| 24 | * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH- |
24 | * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH- |
| 25 | * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
25 | * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
| 26 | * OF THE POSSIBILITY OF SUCH DAMAGE. |
26 | * OF THE POSSIBILITY OF SUCH DAMAGE. |
|
|
27 | * |
|
|
28 | * Alternatively, the contents of this file may be used under the terms of |
|
|
29 | * the GNU General Public License version 2 (the "GPL"), in which case the |
|
|
30 | * provisions of the GPL are applicable instead of the above. If you wish to |
|
|
31 | * allow the use of your version of this file only under the terms of the |
|
|
32 | * GPL and not to allow others to use your version of this file under the |
|
|
33 | * BSD license, indicate your decision by deleting the provisions above and |
|
|
34 | * replace them with the notice and other provisions required by the GPL. If |
|
|
35 | * you do not delete the provisions above, a recipient may use your version |
|
|
36 | * of this file under either the BSD or the GPL. |
| 27 | */ |
37 | */ |
| 28 | |
38 | |
| 29 | #include "lzfP.h" |
39 | #include "lzfP.h" |
| 30 | |
40 | |
| 31 | #define HSIZE (1 << (HLOG)) |
41 | #define HSIZE (1 << (HLOG)) |
| … | |
… | |
| 36 | * the hashing function might seem strange, just believe me |
46 | * the hashing function might seem strange, just believe me |
| 37 | * it works ;) |
47 | * it works ;) |
| 38 | */ |
48 | */ |
| 39 | #define FRST(p) (((p[0]) << 8) + p[1]) |
49 | #define FRST(p) (((p[0]) << 8) + p[1]) |
| 40 | #define NEXT(v,p) (((v) << 8) + p[2]) |
50 | #define NEXT(v,p) (((v) << 8) + p[2]) |
| 41 | #define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) + h*3) & (HSIZE - 1)) |
51 | #define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) - h*5) & (HSIZE - 1)) |
| 42 | /* |
52 | /* |
| 43 | * IDX works because it is very similar to a multiplicative hash, e.g. |
53 | * IDX works because it is very similar to a multiplicative hash, e.g. |
| 44 | * (h * 57321 >> (3*8 - HLOG)) |
54 | * ((h * 57321 >> (3*8 - HLOG)) & (HSIZE - 1)) |
|
|
55 | * the latter is also quite fast on newer CPUs, and sligthly better |
|
|
56 | * |
| 45 | * the next one is also quite good, albeit slow ;) |
57 | * the next one is also quite good, albeit slow ;) |
| 46 | * (int)(cos(h & 0xffffff) * 1e6) |
58 | * (int)(cos(h & 0xffffff) * 1e6) |
| 47 | */ |
59 | */ |
| 48 | |
60 | |
| 49 | #if 0 |
61 | #if 0 |
| 50 | /* original lzv-like hash function */ |
62 | /* original lzv-like hash function, much worse and thus slower */ |
| 51 | # define FRST(p) (p[0] << 5) ^ p[1] |
63 | # define FRST(p) (p[0] << 5) ^ p[1] |
| 52 | # define NEXT(v,p) ((v) << 5) ^ p[2] |
64 | # define NEXT(v,p) ((v) << 5) ^ p[2] |
| 53 | # define IDX(h) ((h) & (HSIZE - 1)) |
65 | # define IDX(h) ((h) & (HSIZE - 1)) |
| 54 | #endif |
66 | #endif |
| 55 | |
67 | |
