Results 1 to 3 of 3

Thread: Code optimization for adaptive binary predictor

  1. #1
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts

    Code optimization for adaptive binary predictor

    I optimized the adaptive binary predictor code in Matt's fpaqc. The code below shows both old and new.


    void update(int y) {
    #ifdef SLOWPRED

    // original predictor
    if (y) t[cxt]+=65536-t[cxt]>>5;
    else t[cxt]-=t[cxt]>>5;
    #else

    // faster predictor (equivalent)
    t[cxt] -= (t[cxt] - y >> 5) - (-y & 0x7ff);

    #endif
    if ((cxt+=cxt+y)>=512) cxt=1;
    }

  2. The Following User Says Thank You to nburns For This Useful Post:

    Bulat Ziganshin (16th February 2017)

  3. #2
    Member
    Join Date
    Nov 2014
    Location
    California
    Posts
    122
    Thanks
    36
    Thanked 33 Times in 24 Posts
    I had similar code in Kanzi FPAQPredictor.cpp:

    // Update the probability model
    // bit == 1 -> prob += (3*((PSCALE-(prob+16))) >> 7);
    // bit == 0 -> prob -= (3*(prob+16)) >> 7);
    inline void FPAQPredictor::update(int bit)
    {
    _probs[_ctxIdx] -= ((3 * ((_probs[_ctxIdx] + 16) - (PSCALE & -bit))) >> 7);


    if (_ctxIdx < 128 )
    _ctxIdx = (_ctxIdx << 1) | bit;
    else
    _ctxIdx = 1;
    }

  4. #3
    Member
    Join Date
    Feb 2013
    Location
    San Diego
    Posts
    1,057
    Thanks
    54
    Thanked 71 Times in 55 Posts
    It looks like it should be possible to make mine a little simpler. I tried just now, but I discovered how subtle and fragile that is (I wrote it a few years ago).

    EDIT: There are a lot of annoying problems that can crop up when right shifting (signed vs unsigned, rounding), so I guess that's why the version in the OP looks the way it does.

    @hexagone You are probably ignoring the fact that right-shifting has funny rounding behavior on negative numbers, because in your case it probably doesn't matter.
    Last edited by nburns; 17th February 2017 at 03:33.

Similar Threads

  1. Adaptive Lossless Prediction impl in C++
    By mo_ in forum Data Compression
    Replies: 1
    Last Post: 26th January 2017, 06:49
  2. Binary Size-Optimization Algorithm Idea
    By paqfan in forum Data Compression
    Replies: 11
    Last Post: 19th March 2012, 16:41
  3. Adaptive adaptation rate :)
    By Piotr Tarsa in forum Data Compression
    Replies: 29
    Last Post: 6th January 2012, 16:44
  4. Advanced counter/predictor
    By encode in forum Data Compression
    Replies: 22
    Last Post: 27th May 2008, 23:43
  5. PREDICTOR algorithm
    By encode in forum Forum Archive
    Replies: 30
    Last Post: 16th February 2008, 19:28

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •