Follow @nxtchg

Author Topic: Code snippets  (Read 2993 times)

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Code snippets
« on: January 23, 2015, 10:54:31 pm »
0
God, how I love to write concise code!

Code: [Select]
    if(cmd == "open vault")
    {
        sim_open_vault &c = *(sim_open_vault*)&cmd;

        char *path = os::expand_path(c.filename);

        if(!vault.load(path, c.password)) cmd.failed(vault.error);

        return true;
    }
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #1 on: January 24, 2015, 09:45:09 am »
0
It might seem obvious to you, but the same code could be written like this:

Code: [Select]
if(strcmp(incom_pCmd->getType(), "open vault") == 0)
{
SimCmd_OpenVault *lpOpenVaultCmd = dynamic_cast<SimCmd_OpenVault*>incom_pCmd;

static outExtVaultPath[MAX_PATH];

opsys::expandPath(lpOpenVaultCmd->pFileName, outExtVaultPath, MAX_PATH-1);

DWORD _retCode = m_VaultCont.loadVault(outExtVaultPath, lpOpenVaultCmd->pVaultPassword);
if(_retCode == SIM_VAULT_LOAD_ERROR)
{
TCHAR vErrorInfo[m_VaultCont::MAX_VAULT_ERROR_LENGTH];

m_VaultCont.GetExtErrorInfo(*vErrorInfo);
incom_pCmd->setReturnStatus(vErrorInfo);
}

return (SIM_COMMAND_STATUS_PROCESSED);
}

So any time I can write something with absolute minimum amount of noise, it makes me happy :)
Tentacle Overlord, The Deranged Genius of The Abyss

wizzardTim

  • Jr. Minion
  • **
  • Posts: 80
  • Respect: +5
    • View Profile
Re: Code snippets
« Reply #2 on: February 07, 2015, 11:01:50 pm »
0
Such clean code deserves the extra time and effort, from many perspectives (expendability, readability etc).

Well done!

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #3 on: February 08, 2015, 09:08:52 am »
0
Yeah, I hope so too.
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #4 on: February 14, 2015, 12:22:13 pm »
0
Code: [Select]
void T_Ini::wake_up()
{
wake_me_in(30 Seconds);

if(!ini.changed()) return;

if(!ini.reload()){ sim.log("!Failed to reload INI!"); return; }

sim.log("+INI file loaded.");

sim.cfg_loaded();
}

Why almost nobody writes C code like this? :(

Not boasting, just really upset. I read a ton of code and it's always such a pain to read...
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #5 on: March 18, 2015, 06:53:17 pm »
0
Ever wondered how to calculate CRC32 without that annoying 1Kb lookup table?

Code: [Select]
static uint crc32_tab[] = {
0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
};

uint crc32(byte *data, int size)
{
uint crc = ~0;

while(size--)
crc = crc32_tab[(crc ^ *data++) & 0xFF] ^ (crc >> 8);

return ~crc;
}

Here's how:

Code: [Select]
uint crc32_nt(byte *data, int size)
{
uint r = ~0; byte *end = data + size;

while(data < end)
{
r ^= *data++;

for(int i = 0; i < 8; i++)
{
uint t = ~((r&1) - 1); r = (r>>1) ^ (0xEDB88320 & t);
}
}

return ~r;
}

It will be compiled into tiny code of about 50 bytes:

Code: [Select]
push esi
lea esi, DWORD PTR [ecx+edx]
or eax, -1
cmp ecx, esi
jae SHORT $L1193
push edi
$L1192:
xor edx, edx
mov dl, BYTE PTR [ecx]
xor eax, edx
inc ecx
mov edx, 8
$L1195:
mov edi, eax
and edi, 1
dec edi
not edi
and edi, -306674912 ; edb88320H
shr eax, 1
xor eax, edi
dec edx
jne SHORT $L1195
cmp ecx, esi
jb SHORT $L1192
pop edi
$L1193:
not eax
pop esi
ret 0

Beautiful.

Why do I bother? I thought it would be nice to add a simple checksum into VM's bytecode, the one which can be easily checked from PHP or JS without the need for Blake2s hash function.
Tentacle Overlord, The Deranged Genius of The Abyss

dzarmush

  • Jr. Minion
  • **
  • Posts: 89
  • Respect: +8
    • View Profile
Re: Code snippets
« Reply #6 on: March 19, 2015, 02:07:10 pm »
0
it's_beautiful.jpg

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #7 on: February 26, 2017, 08:21:07 am »
0
In Simcoin I often need to limit access to some resource by a fixed rate to manage CPU load. For example, if some peer starts spamming us with packets, we better drop most of them, instead of trying to process them.

Turns out throttling is not that simple. If you simply measure time from the last request and drop any requests, which come sooner, you will have a terrible algorithm.

What you want is an algorithm, which maintains a fixed average rate and allows significant variability in timings. The algorithm should be simple, with little memory footprint, because we need to cache a lot of peers in memory, and each one needs a throttler.

Here's a simple class I came up with and kinda proud of it :)

It seems to be very accurate, yet simple, and only takes 8 bytes. Maybe you will find it useful too.

Code: [Select]
//=============================================================================
// Throttler
//=============================================================================
/*
    Class to throttle access to something. Use for up to ~10 K requests/sec.

    Tolerates random +-50% well, so long as it's centered on base_interval.
*/
class Throttler
{
 private: uint64 last_time; // we use 4 lowest bits for 'load': [0,15] => [-7,+8]

int   load(){ return (last_time &  15); }
uint64  ts(){ return (last_time & -16); }

void set(int load, uint64 ts){ last_time = (ts & -16) | load; }

 public:

Throttler(){ last_time = 0; }

bool too_soon(const float base_interval); // in ms
};//___________________________________________________________________________

bool Throttler::too_soon(const float base_interval)
{
const int64 tsv = ts(); msecs prev, t = now;

if(tsv == 0){ set(7, t.value); return false; } // first request, just record time (7 is our mid-point, i.e. "0")

prev.value = tsv;

const float dt = t - prev; // time since last request, ms

if(dt < base_interval * 0.125f) return true; // we skip requests which are too fast for our 'load' resolution (1/8)

const float remainder = (base_interval - dt) * 8 / base_interval; // we split base_interval into 8 steps

bool r = false; int ld = load() + f2i(remainder); // we accumulate deficit or surplus

if(ld > 15){ r = true; ld -= 8; if(ld > 15) ld = 15; } // we've accumulated the whole base_interval or more -> skip this request
if(ld <  0){ ld = 0; }

set(ld, t.value);
 
return r;
}
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #8 on: February 28, 2017, 09:22:47 am »
0
CRC-4 if you ever need it:

Code: [Select]
byte crc4(void *data, int size) // CRC-4-ITU
{
    byte r = 0, *p = (byte*)data, *end = p + size;

    while(p < end)
    {
        r ^= *p++;

        till(8){ const int t = ~((r&1) - 1); r = (r>>1) ^ (0xC & t); } // can be unrolled
    }
   
    return r;
}
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #9 on: April 12, 2017, 09:11:20 am »
0
Double-linked list. Ain't it a beauty?..

Code: [Select]
template<class thing>
class list
{
 private: thing *head, *tail;
 public:
    list(){ empty(); }

    thing* first(){ return head; } // top
    thing*  last(){ return tail; } // bottom

    void insert(thing *p, char *at = "top")
    {
        if(*at == 't'){ p->prev = null; p->next = head; head = p; if(!tail) tail = p; }
        else          { p->next = null; p->prev = tail; tail = p; if(!head) head = p; }
    }

    thing* remove(thing *p)
    {
        if(p->prev) p->prev->next = p->next;
        if(p->next) p->next->prev = p->prev;
   
        if(p == head) head = p->next;
        if(p == tail) tail = p->prev;

        return p;
    }

    thing* remove(char *at){ return remove(*at == 't' ? first() : last()); }

    void move(thing *p, char *at){ remove(p); insert(p, at); }

    void empty(){ tail = head = null; }
};
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Calculating Median
« Reply #10 on: May 01, 2017, 05:05:38 pm »
0
There are two well-known ways to calculate median:

1. naive way (sort, pick the middle)
2. using quickselect (https://en.wikipedia.org/wiki/Quickselect or in case of weighted median: https://en.wikipedia.org/wiki/Weighted_median)

Both these ways are not very suitable for our time sync:
* they require a copy of the original nodes array
* they are both pretty slow

It is reasonable to expect that time votes from our nodes will follow a normal distribution. Indeed, computers usually do: http://vancouver-webpages.com/time/

We can exploit this fact and write a linear algorithm, which works in O(n).

Here's how:
* find the mean
* set current partition point to it
* repeat until the median is found:
   * go through array and count weights of all the elements above, below or equal to the partition point
   * at the same time find the closest item above and the closest item below the partition point
   * if we found the median, return it, otherwise set the partition point to the item above/below and try again

You get a simple and elegant function, which usually finishes in 3 iterations.

Here's the code (includes mean and mean median):

Code: [Select]
/*
 These functions calculate weighted mean, median and mean median of an array.

 Your objects must have mm_value(int no) and mm_weight() functions, which
 return the same type.
*/

template<class thing, class object>
thing stat_mean(array<object> &data, thing center = 0, thing range = 0, int no = 0)
{
    double mean = 0, weight = 0;

    const thing lo = center - range;
    const thing hi = center + range;

    till(data.size())
    {
        thing w   = data[i].mm_weight( ); if(w <= 0) continue;
        thing val = data[i].mm_value(no);
       
        if(range > 0) val = clamp(val, lo, hi);

        mean += double(val) * w; weight += w;
    }

    return (thing)(weight ? mean / weight : 0);
}//____________________________________________________________________________
/*
 This function works best when the median is close to the mean, then it works
 in O(n). Usually this is the case, so we do it this way to avoid sorting or
 changing the original array. Worst case performance can be ~O((n^2)/2).
*/

template<class thing, class object>
thing stat_median(array<object> &data, int no = 0)
{
    thing below, above, equal = stat_mean<thing>(data, 0, 0, no);

    while(true)
    {
        double below_w = 0, equal_w = 0, above_w = 0;

        till(data.size())
        {
            thing w   = data[i].mm_weight( ); if(w <= 0) continue;
            thing val = data[i].mm_value(no);

            if(val > equal){ if(above_w == 0 || val < above){ above = val; } above_w += w; } else
            if(val < equal){ if(below_w == 0 || val > below){ below = val; } below_w += w; }
            else//== equal
                equal_w += w;
        }

        double mid = (below_w + equal_w + above_w);
       
        if(mid > 0) mid /= 2; else return 0;

        if(mid >= below_w)
        {
            if(mid <= below_w + equal_w) return (mid == below_w ? below : equal);

            equal = above;
        }
        else
            equal = below;
    }

    return 0;
}//____________________________________________________________________________

template<class thing, class object>
thing stat_mean_median(array<object> &data, thing range, int no = 0)
{
    thing median = stat_median<thing>(data, no);

    return stat_mean<thing>(data, median, range, no);
}

Everything in just 63 lines of code :)
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Cached median calculation
« Reply #11 on: May 06, 2017, 07:45:01 am »
0
The simple median calculation algorithm above works great when values are far apart and are centered on the mean.
But performance drops quickly as the number of nodes increases and their time votes converge.

So I had to improve the original algorithm by adding a simple cache to sort a small core of the data set.

Now it works as fast as regular "copy/sort/pick" algorithm, but doesn't change the original array:

Code: [Select]
template<class thing, int sz = 30*2+1>
class MedianCache
{
 public:
        class Item
        {
         public: thing val, w;

            bool is_free(){ return (w == 0); }

            bool operator< (thing v){ return (w != 0 && val < v); }
            bool operator> (thing v){ return (w != 0 && val > v); }

        } item[sz]; double below_w, above_w;

    void init(thing mean){ above_w = below_w = 0; base().val = mean; till(dimof(item)) item[i].w = 0;  }

    Item&  bot(){ return item[     0]; }
    Item& base(){ return item[sz >>1]; }
    Item&  top(){ return item[sz - 1]; }

    bool above(double mid){ return (mid <= above_w); }
    bool below(double mid){ return (mid <= below_w); }

    void swap(Item &a, Item &b){ Item t = a; a = b; b = t; }

    void add(thing val, thing w)
    {
        if(top() < val){ above_w += w; return; }
        if(bot() > val){ below_w += w; return; }

        Item it; it.val = val; it.w = w;

        if(val > base().val)
        {
            for(int i = (sz >> 1) + 1; i < sz; i++)
            {
                if(item[i].is_free()){ item[i] = it; return; }

                if(item[i].val > it.val) swap(item[i], it);
            }

            above_w += it.w; // evict top
        }
        else if(val < base().val)
        {
            for(int i = (sz >> 1) - 1; i >= 0; i--)
            {
                if(item[i].is_free()){ item[i] = it; return; }

                if(item[i].val < it.val) swap(item[i], it);
            }

            below_w += it.w; // evict bot
        }
        else base().w += w; // val == base().val
    }

    thing median(double mid)
    {
        mid -= below_w; till(dimof(item)){ mid -= item[i].w; if(mid <= 0) return item[i].val; }
    }
};//___________________________________________________________________________

template<class thing, class object>
thing stat_median(array<object> &data, int no = 0)
{
    double mid = 0;

    thing base = stat_mean<thing>(data, 0, 0, no, 0, &mid);

    if(mid > 0) mid /= 2; else return 0;

    MedianCache<thing, 50*2+1> cache;

    while(true)
    {
        cache.init(base);

        till(data.size()){ thing w = data[i].mm_weight(); if(w > 0) cache.add(data[i].mm_value(no), w); }

        if(cache.below(mid)){ base = cache.bot().val; continue; }
        if(cache.above(mid)){ base = cache.top().val; continue; }
       
        return cache.median(mid);
    }
}

For 1000 nodes the cache size of 100 is enough to calculate the median in just one pass.
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Cookies in Javascript
« Reply #12 on: June 29, 2017, 05:58:38 pm »
0
Dealing with cookies in Javascript:

Code: [Select]
function get_cookie(name)
{
    var arr = document.cookie.split(';');

    for(var i = 0; i < arr.length; i++)
    {
        var c = arr[i], p = -1; while(c.charCodeAt(++p) < 33);

        if(c.indexOf(name+'=', p) == p)
        {
            return decodeURIComponent(c.substr(p + name.length + 1));
        }
    }
}

Code: [Select]
function set_cookie(name, val, days, path) // (name, "", -1) to delete a cookie
{
    var enc = encodeURIComponent, v = enc(val);

    if(days)
    {
        var d = new Date(); d.setDate(d.getDate() + days);

        v += '; expires=' + d.toUTCString();
    }

    if(path) v += '; path=' + path;

    document.cookie = enc(name) + '=' + v; // + '; Secure'
}
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #13 on: July 08, 2017, 06:40:49 pm »
0
Debounce and throttle added to jslib: https://github.com/NxtChg/pieces/tree/master/js/jslib

Code: [Select]
js.debounce = function(fn, delay) // execute with delay; if called again sooner the delay is reset
{
    return function()
    {
        clearTimeout(this.timer);

        var self = this, args = arguments;

        this.timer = setTimeout(function(){ fn.apply(self, args); }, delay);
    };
};

Code: [Select]
js.throttle = function(fn, delay, immediate) // execute with delay; if called again sooner the call is ignored
{
    return function()
    {
        if(this.timer) return;

        var self = this, args = arguments;

        if(immediate) fn.apply(self, args);

        this.timer = setTimeout(function(){ self.timer = null; fn.apply(self, args); }, delay);
    };
};
Tentacle Overlord, The Deranged Genius of The Abyss

NxtChg

  • Overlord
  • *****
  • Posts: 1114
  • Respect: +61
    • View Profile
Re: Code snippets
« Reply #14 on: October 16, 2017, 10:17:31 am »
0
Prime numbers generator added to https://github.com/NxtChg/pieces/tree/master/js/jslib:

Code: [Select]
function gen_primes(limit) // limit must fit into a 32-bit integer
{
    var i, inc = 4, p = [2,3], L = limit >> 1; // we only need half of the array, since we don't need to check even numbers

    var bits = new Uint8Array(L);

    for(i = 0; i < L; i ++) bits[i] = 1;

    for(i = 5; i < limit; i += inc)
    {
        if(bits[i>>1])
        {
            p.push(i); for(var j = i * i; j < limit; j += i){ if(j&1) bits[j>>1] = 0; }
        }

        inc = 6 - inc; // 2 and 3 produce {2, 4, 2, 4, ...} iteration pattern
    }

    return p;
}
Tentacle Overlord, The Deranged Genius of The Abyss