Elias omega coding など

eoc.c

/* (c) kristopher tate ; all rights resevered. */
static uint16_t eoc_encode(uint16_t code, uint8_t start, uint8_t binrep[ROUTE_LENGTH])
{
    int i;
    int pos = 0;
    uint8_t bits[4];
    while (code > 1) {
        int len = 0;
        for (int temp = code; temp > 0; temp >>= 1) { /*calculate 1+floor(log2(num))*/
            len++;
        }
        for (i = 0; i < len; i++,pos++) {
            b_assign(bits, pos, (code >> i) & 1);
        }
        code = len - 1; /* switch code to encode the length-1*/
    }
    i = 0;
    while (pos) {
        --pos;
        b_assign(binrep, start+i, b_val(bits, pos));
        i++;
    }
    b_assign(binrep, start+i, 0); /* final zero */
    return start+i+1;
}

static int16_t eoc_decode(int *pos, uint8_t binrep[ROUTE_LENGTH])
{
    if (*pos > ROUTE_LENGTH) return 0;
    int num = 1;
    while (b_val(binrep, (*pos)++)) {
        int len = num;
        num = 1;
        for (int i = 0; i < len; ++i) {
            num <<= 1;
            if (b_val(binrep, (*pos)++))
                num |= 1;
        }
    }
    if (num == 1 && *pos > 0) return 0;
    return num;
}

static uint16_t biject_forward(int16_t number)
{
    bool neg = false;
    /* 0, 1, -1, 2, -2 */
    /* 1, 2,  3, 4,  5 */
    if (!number) return 1;
    if (number < 0) {
        neg = true;
        number *= -1;
    }
    return (number * 2) + (neg?1:0);
}

static int16_t biject_reverse(uint16_t number)
{
    /* 1, 2,  3, 4,  5 */
    /* 0, 1, -1, 2, -2 */
    if (number == 1) return 0;
    if (number%2) { /* process negative */
        return -((number - 1) / 2);
    } else {
        return number / 2;
    }
}

static int eoc_translate(uint8_t binrep[ROUTE_LENGTH], int16_t trans)
{
    int pos = 0;
    int number = 0;
    uint16_t encpos = 0;
    uint8_t routetranslate[ROUTE_LENGTH];
    memset(routetranslate, 0, ROUTE_LENGTH);
    while (pos < ROUTE_LENGTH) {
        number = eoc_decode(&pos, binrep);
        if (!number) break;
        number = biject_forward(biject_reverse(number) * trans);
        encpos = eoc_encode(number, encpos, routetranslate);
    }
    memcpy(binrep, routetranslate, ROUTE_LENGTH);
    return encpos;
}

static int label_linf_diff(uint8_t left[ROUTE_LENGTH], uint8_t right[ROUTE_LENGTH])
{
    int lpos = 0;
    int rpos = 0;
    int lnum = 0;
    int rnum = 0;
    int score = 0;
    while (lpos < ROUTE_LENGTH) {
        lnum = eoc_decode(&lpos, left);
        rnum = eoc_decode(&rpos, right);
        debug("lnum = %d ; rnum = %d\n", lnum, rnum);
        if (!lnum || !rnum) break;
        score += abs(lnum - rnum);
    }
    return score;
}