diff options
Diffstat (limited to 'src/set/ibf_sim.c')
-rw-r--r-- | src/set/ibf_sim.c | 119 |
1 files changed, 60 insertions, 59 deletions
diff --git a/src/set/ibf_sim.c b/src/set/ibf_sim.c index d05e06188..02b675f4a 100644 --- a/src/set/ibf_sim.c +++ b/src/set/ibf_sim.c | |||
@@ -11,12 +11,12 @@ | |||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | 11 | WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 | Affero General Public License for more details. | 13 | Affero General Public License for more details. |
14 | 14 | ||
15 | You should have received a copy of the GNU Affero General Public License | 15 | You should have received a copy of the GNU Affero General Public License |
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | 17 | ||
18 | SPDX-License-Identifier: AGPL3.0-or-later | 18 | SPDX-License-Identifier: AGPL3.0-or-later |
19 | */ | 19 | */ |
20 | 20 | ||
21 | /** | 21 | /** |
22 | * @file set/ibf_sim.c | 22 | * @file set/ibf_sim.c |
@@ -62,76 +62,77 @@ main(int argc, char **argv) | |||
62 | unsigned int want; | 62 | unsigned int want; |
63 | double predict; | 63 | double predict; |
64 | 64 | ||
65 | srandom (time (NULL)); | 65 | srandom(time(NULL)); |
66 | total = 0; | 66 | total = 0; |
67 | want = atoi (argv[1]); | 67 | want = atoi(argv[1]); |
68 | for (round=0;round<ROUNDS;round++) | 68 | for (round = 0; round < ROUNDS; round++) |
69 | { | ||
70 | memset (buckets, 0, sizeof (buckets)); | ||
71 | for (i=0;i<want;i++) | ||
72 | { | 69 | { |
73 | /* FIXME: might want to use 'better' PRNG to avoid | 70 | memset(buckets, 0, sizeof(buckets)); |
74 | PRNG-induced biases */ | 71 | for (i = 0; i < want; i++) |
75 | r = random (); | 72 | { |
76 | if (0 == r) | 73 | /* FIXME: might want to use 'better' PRNG to avoid |
77 | continue; | 74 | PRNG-induced biases */ |
75 | r = random(); | ||
76 | if (0 == r) | ||
77 | continue; | ||
78 | #if SLOW | 78 | #if SLOW |
79 | for (j=0;(j < 31) && (0 == (r & (1 << j)));j++) ; | 79 | for (j = 0; (j < 31) && (0 == (r & (1 << j))); j++) |
80 | ; | ||
80 | #else | 81 | #else |
81 | /* use assembly / gcc */ | 82 | /* use assembly / gcc */ |
82 | j = __builtin_ffs (r) - 1; | 83 | j = __builtin_ffs(r) - 1; |
83 | #endif | 84 | #endif |
84 | buckets[j]++; | 85 | buckets[j]++; |
85 | } | 86 | } |
86 | ret = 0; | 87 | ret = 0; |
87 | predict = 0.0; | 88 | predict = 0.0; |
88 | for (j=31;j >= 0; j--) | 89 | for (j = 31; j >= 0; j--) |
89 | { | 90 | { |
90 | #if FIX1 | 91 | #if FIX1 |
91 | /* improved algorithm, for 1000 elements with IBF-DECODE 8, I | 92 | /* improved algorithm, for 1000 elements with IBF-DECODE 8, I |
92 | get 990/1000 elements on average over 1 million runs; key | 93 | get 990/1000 elements on average over 1 million runs; key |
93 | idea being to stop short of the 'last' possible IBF as | 94 | idea being to stop short of the 'last' possible IBF as |
94 | otherwise a "lowball" per-chance would unduely influence the | 95 | otherwise a "lowball" per-chance would unduely influence the |
95 | result */ | 96 | result */ |
96 | if ( (j > 0) && | 97 | if ((j > 0) && |
97 | (buckets[j - 1] > MAX_IBF_DECODE) ) | 98 | (buckets[j - 1] > MAX_IBF_DECODE)) |
98 | { | 99 | { |
99 | ret *= (1 << (j + 1)); | 100 | ret *= (1 << (j + 1)); |
100 | break; | 101 | break; |
101 | } | 102 | } |
102 | #endif | 103 | #endif |
103 | #if FIX2 | 104 | #if FIX2 |
104 | /* another improvement: don't just always cut off the last one, | 105 | /* another improvement: don't just always cut off the last one, |
105 | but rather try to predict based on all previous values where | 106 | but rather try to predict based on all previous values where |
106 | that "last" one is; additional prediction can only really | 107 | that "last" one is; additional prediction can only really |
107 | work if MAX_IBF_DECODE is sufficiently high */ | 108 | work if MAX_IBF_DECODE is sufficiently high */ |
108 | if ( (j > 0) && | 109 | if ((j > 0) && |
109 | ( (buckets[j - 1] > MAX_IBF_DECODE) || | 110 | ((buckets[j - 1] > MAX_IBF_DECODE) || |
110 | (predict > MAX_IBF_DECODE) ) ) | 111 | (predict > MAX_IBF_DECODE))) |
111 | { | 112 | { |
112 | ret *= (1 << (j + 1)); | 113 | ret *= (1 << (j + 1)); |
113 | break; | 114 | break; |
114 | } | 115 | } |
115 | #endif | 116 | #endif |
116 | #if STRATA | 117 | #if STRATA |
117 | /* original algorithm, for 1000 elements with IBF-DECODE 8, | 118 | /* original algorithm, for 1000 elements with IBF-DECODE 8, |
118 | I get 920/1000 elements on average over 1 million runs */ | 119 | I get 920/1000 elements on average over 1 million runs */ |
119 | if (buckets[j] > MAX_IBF_DECODE) | 120 | if (buckets[j] > MAX_IBF_DECODE) |
120 | { | 121 | { |
121 | ret *= (1 << (j+1)); | 122 | ret *= (1 << (j + 1)); |
122 | break; | 123 | break; |
123 | } | 124 | } |
124 | #endif | 125 | #endif |
125 | ret += buckets[j]; | 126 | ret += buckets[j]; |
126 | predict = (buckets[j] + 2.0 * predict) / 2.0; | 127 | predict = (buckets[j] + 2.0 * predict) / 2.0; |
127 | } | 128 | } |
128 | #if VERBOSE | 129 | #if VERBOSE |
129 | fprintf (stderr, "%u ", ret); | 130 | fprintf(stderr, "%u ", ret); |
130 | #endif | 131 | #endif |
131 | total += ret; | 132 | total += ret; |
132 | } | 133 | } |
133 | fprintf (stderr, "\n"); | 134 | fprintf(stderr, "\n"); |
134 | fprintf (stdout, "average %llu\n", total / ROUNDS); | 135 | fprintf(stdout, "average %llu\n", total / ROUNDS); |
135 | return 0; | 136 | return 0; |
136 | } | 137 | } |
137 | 138 | ||