00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include <stdlib.h>
00022 #include <stdio.h>
00023 #include "arith.h"
00024
00025 int l2(unsigned long x) {
00026 static char table[256] = {
00027 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
00028 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
00029 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00030 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
00031 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00032 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00033 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00034 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
00035 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00036 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00037 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00038 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00039 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00040 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00041 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
00042 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
00043 };
00044
00045 #if __WORDSIZE == 64
00046 if (x >> 32)
00047 if (x >> 48)
00048 if (x >> 56)
00049 return table[x >> 56] + 56;
00050 else
00051 return table[x >> 48] + 48;
00052 else if (x >> 40)
00053 return table[x >> 40] + 40;
00054 else
00055 return table[x >> 32] + 32;
00056 else
00057 #endif
00058 if (x >> 16)
00059 if (x >> 24)
00060 return table[x >> 24] + 24;
00061 else
00062 return table[x >> 16] + 16;
00063 else if (x >> 8)
00064 return table[x >> 8] + 8;
00065 else
00066 return table[x];
00067 }
00068
00069 arith_t arith_init(struct buff * b) {
00070 arith_t state;
00071
00072 state = (arith_t) malloc(sizeof (struct code_arith));
00073
00074 state->min = 0;
00075 state->max = (1UL << PREC_INTER);
00076 state->compteur = 0;
00077 state->buffer = b;
00078
00079 return state;
00080 }
00081
00082 int ajuster(arith_t state, int coder) {
00083 int i, j;
00084 unsigned long x;
00085
00086
00087
00088
00089
00090
00091 x = (state->max - 1) ^ state->min;
00092 i = PREC_INTER - l2(x);
00093
00094
00095
00096
00097 x = (state->max - 1) - state->min;
00098 j = PREC_INTER - l2(x) - 1;
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110 if (i > j)
00111 i = j;
00112 if (i > 0) {
00113 if (coder) {
00114 x = state->min >> (PREC_INTER - 1);
00115 state->min &= ~(1UL << (PREC_INTER - 1));
00116 bwrite_bit(x, state->buffer);
00117 bwrite_bits(1 - x, state->compteur, state->buffer);
00118 bwrite(state->min >> (PREC_INTER - i), i - 1, state->buffer);
00119 }
00120 state->compteur = 0;
00121 }
00122 state->max = (state->max << j) & ((1UL << PREC_INTER) - 1);
00123 if (state->max == 0)
00124 state->max = 1UL << PREC_INTER;
00125 state->min = (state->min << j) & ((1UL << PREC_INTER) - 1);
00126 if (j - i > 0) {
00127 state->max ^= (1UL << (PREC_INTER - 1));
00128 state->min ^= (1UL << (PREC_INTER - 1));
00129 state->compteur += j - i;
00130 }
00131
00132 return j;
00133 }
00134
00135
00136
00137 int coder(int i, distrib_t d, arith_t state) {
00138 unsigned long x;
00139 unsigned long delta;
00140 int l;
00141
00142 #ifdef DEBUG
00143 printf("%u\t%u\t%u\n", state->min, state->max, i);
00144 #endif
00145
00146 delta = state->max - state->min;
00147
00148
00149 bwrite_lock(PREC_INTER + state->compteur, state->buffer);
00150
00151 if (i < d.max) {
00152 x = distrib_get_proba(d, i + 1);
00153 x *= delta;
00154 x >>= PREC_PROBA;
00155 state->max = state->min + x;
00156 }
00157 x = distrib_get_proba(d, i);
00158 x *= delta;
00159 x >>= PREC_PROBA;
00160 state->min += x;
00161
00162 #ifdef DEBUG
00163 printf("%u\t%u\n", state->min, state->max);
00164 #endif
00165
00166 l = ajuster(state, 1);
00167
00168 #ifdef DEBUG
00169 printf("%u\t%u\n", state->min, state->max);
00170 #endif
00171
00172 return l;
00173 }
00174
00175
00176 int coder_uniforme(unsigned long i, unsigned long n, arith_t state) {
00177 unsigned long x;
00178 unsigned long delta;
00179 int l;
00180
00181 #ifdef DEBUG
00182 printf("%u\t%u\t%u\t*%u\n", state->min, state->max, i, n);
00183 #endif
00184
00185 delta = state->max - state->min;
00186
00187
00188 bwrite_lock(PREC_INTER + state->compteur, state->buffer);
00189
00190 x = i;
00191 x *= delta;
00192
00193 state->max = state->min + ((x + delta) / n);
00194 state->min += x / n;
00195
00196 #ifdef DEBUG
00197 printf("%u\t%u\n", state->min, state->max);
00198 #endif
00199
00200 l = ajuster(state, 1);
00201
00202 #ifdef DEBUG
00203 printf("%u\t%u\n", state->min, state->max);
00204 #endif
00205
00206 return l;
00207 }
00208
00209 int chercher(unsigned long valeur, unsigned long * sprob, int a, int b) {
00210 if (b - a == 1)
00211 return a;
00212 else {
00213 int m = (a + b) / 2;
00214 if (sprob[m] > valeur)
00215 return chercher(valeur, sprob, a, m);
00216 else
00217 return chercher(valeur, sprob, m, b);
00218 }
00219 }
00220
00221
00222
00223 int decoder(distrib_t d, int * lettre, arith_t state) {
00224 unsigned long x;
00225 unsigned long delta, valeur;
00226 int i, r;
00227
00228 delta = state->max - state->min;
00229
00230 if (state->compteur)
00231 valeur = blook(PREC_INTER, state->buffer) ^ (1UL << (PREC_INTER - 1));
00232 else
00233 valeur = blook(PREC_INTER, state->buffer);
00234
00235 bread_lock(PREC_INTER, state->buffer);
00236
00237 x = valeur - state->min;
00238 x <<= PREC_PROBA;
00239 x /= delta;
00240
00241 i = d.min + chercher(x, d.prob, 0, d.max - d.min + 1);
00242
00243 #ifdef DEBUG
00244 printf("%u\t%u\t", state->min, state->max);
00245 #endif
00246
00247 if (i < d.max) {
00248 x = distrib_get_proba(d, i + 1);
00249 x *= delta;
00250 x >>= PREC_PROBA;
00251 x += state->min;
00252 if (valeur >= x) {
00253 ++i;
00254 if (i < d.max) {
00255 x = distrib_get_proba(d, i + 1);
00256 x *= delta;
00257 x >>= PREC_PROBA;
00258 state->max = state->min + x;
00259 }
00260 }
00261 else
00262 state->max = x;
00263 }
00264 x = distrib_get_proba(d, i);
00265 x *= delta;
00266 x >>= PREC_PROBA;
00267 state->min += x;
00268
00269 #ifdef DEBUG
00270 printf("%u\t%u\n", i, valeur);
00271 #endif
00272
00273 #ifdef DEBUG
00274 printf("%u\t%u\n", state->min, state->max);
00275 #endif
00276
00277 r = ajuster(state, 0);
00278 bstep(r, state->buffer);
00279
00280 #ifdef DEBUG
00281 printf("%u\t%u\n", state->min, state->max);
00282 #endif
00283
00284 *lettre = i;
00285 return r;
00286 }
00287
00288
00289 unsigned long decoder_uniforme(unsigned long n, unsigned long * lettre, arith_t state) {
00290 unsigned long x;
00291 unsigned long delta, valeur;
00292 int i, r;
00293
00294 delta = state->max - state->min;
00295
00296 if (state->compteur)
00297 valeur = blook(PREC_INTER, state->buffer) ^ (1UL << (PREC_INTER - 1));
00298 else
00299 valeur = blook(PREC_INTER, state->buffer);
00300
00301 bread_lock(PREC_INTER, state->buffer);
00302
00303 x = valeur - state->min;
00304 x *= n;
00305 x /= delta;
00306 i = x;
00307
00308 #ifdef DEBUG
00309 printf("%u\t%u\t", state->min, state->max);
00310 #endif
00311
00312 x = i;
00313 x *= delta;
00314 state->max = state->min + ((x + delta) / n);
00315
00316 if (valeur >= state->max) {
00317 ++i;
00318 x += delta;
00319 state->max = state->min + ((x + delta) / n);
00320 }
00321 state->min += x / n;
00322
00323 #ifdef DEBUG
00324 printf("%u\t*%u\n", i, n);
00325 #endif
00326
00327 #ifdef DEBUG
00328 printf("%u\t%u\n", state->min, state->max);
00329 #endif
00330
00331 r = ajuster(state, 0);
00332 bstep(r, state->buffer);
00333
00334 #ifdef DEBUG
00335 printf("%u\t%u\n", state->min, state->max);
00336 #endif
00337
00338 *lettre = i;
00339 return r;
00340 }