summaryrefslogtreecommitdiff
path: root/src/set/ibf_sim.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/set/ibf_sim.c')
-rw-r--r--src/set/ibf_sim.c119
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