forked from JeanLucPons/Kangaroo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
HashTable.h
104 lines (79 loc) · 2.67 KB
/
HashTable.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/*
* This file is part of the BSGS distribution (https://github.com/JeanLucPons/Kangaroo).
* Copyright (c) 2020 Jean Luc PONS.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, version 3.
*
* This program 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
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef HASHTABLEH
#define HASHTABLEH
#include <string>
#include <vector>
#include "SECPK1/Point.h"
#ifdef WIN64
#include <Windows.h>
#endif
#define HASH_SIZE_BIT 18
#define HASH_SIZE (1<<HASH_SIZE_BIT)
#define HASH_MASK (HASH_SIZE-1)
#define ADD_OK 0
#define ADD_DUPLICATE 1
#define ADD_COLLISION 2
union int128_s {
uint8_t i8[16];
uint16_t i16[8];
uint32_t i32[4];
uint64_t i64[2];
};
typedef union int128_s int128_t;
#define safe_free(x) if(x) {free(x);x=NULL;}
// We store only 128 (+18) bit a the x value which give a probabilty a wrong collision after 2^73 entries
typedef struct {
int128_t x; // Poisition of kangaroo (128bit LSB)
int128_t d; // Travelled distance (b127=sign b126=kangaroo type, b125..b0 distance
} ENTRY;
typedef struct {
uint32_t nbItem;
uint32_t maxItem;
ENTRY **items;
} HASH_ENTRY;
class HashTable {
public:
HashTable();
int Add(Int *x,Int *d,uint32_t type);
int Add(uint64_t h,int128_t *x,int128_t *d);
int Add(uint64_t h,ENTRY *e);
uint64_t GetNbItem();
void Reset();
std::string GetSizeInfo();
void PrintInfo();
void SaveTable(FILE *f);
void SaveTable(FILE* f,uint32_t from,uint32_t to,bool printPoint=true);
void LoadTable(FILE *f);
void LoadTable(FILE* f,uint32_t from,uint32_t to);
void ReAllocate(uint64_t h,uint32_t add);
void SeekNbItem(FILE* f,bool restorePos = false);
void SeekNbItem(FILE* f,uint32_t from,uint32_t to);
HASH_ENTRY E[HASH_SIZE];
// Collision info
Int kDist;
uint32_t kType;
static void Convert(Int *x,Int *d,uint32_t type,uint64_t *h,int128_t *X,int128_t *D);
static int MergeH(uint32_t h,FILE* f1,FILE* f2,FILE* fd,uint32_t *nbDP,uint32_t* duplicate,
Int* d1,uint32_t* k1,Int* d2,uint32_t* k2);
static void CalcDistAndType(int128_t d,Int* kDist,uint32_t* kType);
private:
ENTRY *CreateEntry(int128_t *x,int128_t *d);
static int compare(int128_t *i1,int128_t *i2);
std::string GetStr(int128_t *i);
};
#endif // HASHTABLEH