crema-cli 0.1.0

use crate::math::full_math::FullMath;

pub const MIN_TICK: i32 = -443636;
pub const MAX_TICK: i32 = -MIN_TICK;

pub const MAX_SQRT_PRICE_X64: u128 = 79226673515401279992447579055;
pub const MIN_SQRT_PRICE_X64: u128 = 4295048016;

pub fn get_sqrt_price_at_tick(tick: i32) -> u128 {
    if tick >= 0 {
        get_sqrt_price_at_positive_tick(tick)
    } else {
        get_sqrt_price_at_negative_tick(tick)
    }
}

fn get_sqrt_price_at_negative_tick(tick: i32) -> u128 {
    let abs_tick = tick.abs();

    let mut ratio: u128 = if abs_tick & 0x1 != 0 {
        18445821805675392311u128
    } else {
        18446744073709551616u128
    };

    const SHIFT_64: u32 = 64;
    if abs_tick & 0x2 != 0 {
        ratio = ratio.mul_shift_right(18444899583751176498u128, SHIFT_64);
    }
    if abs_tick & 0x4 != 0 {
        ratio = ratio.mul_shift_right(18443055278223354162u128, SHIFT_64);
    }
    if abs_tick & 0x8 != 0 {
        ratio = ratio.mul_shift_right(18439367220385604838u128, SHIFT_64);
    }
    if abs_tick & 0x10 != 0 {
        ratio = ratio.mul_shift_right(18431993317065449817u128, SHIFT_64);
    }
    if abs_tick & 0x20 != 0 {
        ratio = ratio.mul_shift_right(18417254355718160513u128, SHIFT_64);
    }
    if abs_tick & 0x40 != 0 {
        ratio = ratio.mul_shift_right(18387811781193591352u128, SHIFT_64);
    }
    if abs_tick & 0x80 != 0 {
        ratio = ratio.mul_shift_right(18329067761203520168u128, SHIFT_64);
    }
    if abs_tick & 0x100 != 0 {
        ratio = ratio.mul_shift_right(18212142134806087854u128, SHIFT_64);
    }
    if abs_tick & 0x200 != 0 {
        ratio = ratio.mul_shift_right(17980523815641551639u128, SHIFT_64);
    }
    if abs_tick & 0x400 != 0 {
        ratio = ratio.mul_shift_right(17526086738831147013u128, SHIFT_64);
    }
    if abs_tick & 0x800 != 0 {
        ratio = ratio.mul_shift_right(16651378430235024244u128, SHIFT_64);
    }
    if abs_tick & 0x1000 != 0 {
        ratio = ratio.mul_shift_right(15030750278693429944u128, SHIFT_64);
    }
    if abs_tick & 0x2000 != 0 {
        ratio = ratio.mul_shift_right(12247334978882834399u128, SHIFT_64);
    }
    if abs_tick & 0x4000 != 0 {
        ratio = ratio.mul_shift_right(8131365268884726200u128, SHIFT_64);
    }
    if abs_tick & 0x8000 != 0 {
        ratio = ratio.mul_shift_right(3584323654723342297u128, SHIFT_64);
    }
    if abs_tick & 0x10000 != 0 {
        ratio = ratio.mul_shift_right(696457651847595233u128, SHIFT_64);
    }
    if abs_tick & 0x20000 != 0 {
        ratio = ratio.mul_shift_right(26294789957452057u128, SHIFT_64);
    }
    if abs_tick & 0x40000 != 0 {
        ratio = ratio.mul_shift_right(37481735321082u128, SHIFT_64);
    }

    ratio
}

fn get_sqrt_price_at_positive_tick(tick: i32) -> u128 {
    let mut ratio = if tick & 0x1 != 0 {
        79232123823359799118286999567u128
    } else {
        79228162514264337593543950336u128
    };

    const SHIFT_96: u32 = 96;
    if tick & 0x2 != 0 {
        ratio = ratio.mul_shift_right(79236085330515764027303304731u128, SHIFT_96)
    }
    if tick & 0x4 != 0 {
        ratio = ratio.mul_shift_right(79244008939048815603706035061u128, SHIFT_96)
    }
    if tick & 0x8 != 0 {
        ratio = ratio.mul_shift_right(79259858533276714757314932305u128, SHIFT_96)
    }
    if tick & 0x10 != 0 {
        ratio = ratio.mul_shift_right(79291567232598584799939703904u128, SHIFT_96)
    }
    if tick & 0x20 != 0 {
        ratio = ratio.mul_shift_right(79355022692464371645785046466u128, SHIFT_96)
    }
    if tick & 0x40 != 0 {
        ratio = ratio.mul_shift_right(79482085999252804386437311141u128, SHIFT_96)
    }
    if tick & 0x80 != 0 {
        ratio = ratio.mul_shift_right(79736823300114093921829183326u128, SHIFT_96)
    }
    if tick & 0x100 != 0 {
        ratio = ratio.mul_shift_right(80248749790819932309965073892u128, SHIFT_96)
    }
    if tick & 0x200 != 0 {
        ratio = ratio.mul_shift_right(81282483887344747381513967011u128, SHIFT_96)
    }
    if tick & 0x400 != 0 {
        ratio = ratio.mul_shift_right(83390072131320151908154831281u128, SHIFT_96)
    }
    if tick & 0x800 != 0 {
        ratio = ratio.mul_shift_right(87770609709833776024991924138u128, SHIFT_96)
    }
    if tick & 0x1000 != 0 {
        ratio = ratio.mul_shift_right(97234110755111693312479820773u128, SHIFT_96)
    }
    if tick & 0x2000 != 0 {
        ratio = ratio.mul_shift_right(119332217159966728226237229890u128, SHIFT_96)
    }
    if tick & 0x4000 != 0 {
        ratio = ratio.mul_shift_right(179736315981702064433883588727u128, SHIFT_96)
    }
    if tick & 0x8000 != 0 {
        ratio = ratio.mul_shift_right(407748233172238350107850275304u128, SHIFT_96)
    }
    if tick & 0x10000 != 0 {
        ratio = ratio.mul_shift_right(2098478828474011932436660412517u128, SHIFT_96)
    }
    if tick & 0x20000 != 0 {
        ratio = ratio.mul_shift_right(55581415166113811149459800483533u128, SHIFT_96)
    }
    if tick & 0x40000 != 0 {
        ratio = ratio.mul_shift_right(38992368544603139932233054999993551u128, SHIFT_96)
    }

    ratio >> 32
}

pub fn get_tick_at_sqrt_price(sqrt_price_x64: u128) -> i32 {
    let mut r = sqrt_price_x64;
    let mut msb = 0; // in [1, 128)

    // ------------------------------------------------------
    // Decimal part of logarithm = MSB
    // Binary search method: 2^32, 2^16, 2^8, 2^4, 2^2 and 2^1 for U64.64
    let mut f: u8 = ((r >= 0x10000000000000000) as u8) << 6; // If r >= 2^64, f = 64 else 0
    msb |= f;
    r >>= f;

    f = ((r >= 0x100000000) as u8) << 5; // 2^32
    msb |= f; // Add f to MSB
    r >>= f; // Right shift by f

    f = ((r >= 0x10000) as u8) << 4; // 2^16
    msb |= f;
    r >>= f;

    f = ((r >= 0x100) as u8) << 3; // 2^8
    msb |= f;
    r >>= f;

    f = ((r >= 0x10) as u8) << 2; // 2^4
    msb |= f;
    r >>= f;

    f = ((r >= 0x4) as u8) << 1; // 2^2
    msb |= f;
    r >>= f;

    f = ((r >= 0x2) as u8) << 0; // 2^0
    msb |= f;

    // log2 (m x 2^e) = log2 (m) + e
    // For U64.64, e = -64. Subtract by 64 to remove x64 notation.
    // Then left shift by 16 bits to convert into U96.32 form
    let mut log_2_x32 = (msb as i128 - 64) << 32;
    // ------------------------------------------------------
    // Fractional part of logarithm

    // Set r = r / 2^n as a Q65.63 number, where n stands for msb
    r = if msb >= 64 {
        sqrt_price_x64 >> (msb - 63)
    } else {
        sqrt_price_x64 << (63 - msb)
    };

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 31;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 30;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 29;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 28;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 27;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 26;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 25;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 24;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 23;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 22;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 21;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 20;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 19;
    r >>= f;

    r = (r * r) >> 63;
    f = (r >> 64) as u8;
    log_2_x32 |= (f as i128) << 18;

    let log_sqrt_10001 = log_2_x32 * 59543866431366;

    let tick_low = ((log_sqrt_10001 - 184467440737095516) >> 64) as i32;
    let tick_high = ((log_sqrt_10001 + 15793534762490258745) >> 64) as i32;

    if tick_low == tick_high {
        tick_low
    } else if get_sqrt_price_at_tick(tick_high) <= sqrt_price_x64 {
        tick_high
    } else {
        tick_low
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    mod test_get_sqrt_price_at_tick {
        use super::*;

        #[test]
        #[should_panic(expected = "called `Option::unwrap()` on a `None` value")]
        fn tick_exceed_max() {
            let a = get_sqrt_price_at_tick(MAX_TICK + 1);
            let b = get_sqrt_price_at_tick(MAX_TICK);
            println!("{} {}", a, b);
            assert!(get_sqrt_price_at_tick(MAX_TICK + 1) > get_sqrt_price_at_tick(MAX_TICK))
        }

        #[test]
        fn tick_below_min() {
            assert!(get_sqrt_price_at_tick(MIN_TICK - 1) < get_sqrt_price_at_tick(MIN_TICK))
        }

        #[test]
        fn all_sqrt_price_in_tick() {
            for t in MIN_TICK..MAX_TICK {
                let _price = get_sqrt_price_at_tick(t);
                let tick = get_tick_at_sqrt_price(_price);
                if t != tick {
                    assert_eq!(t, tick);
                }
            }
        }

        #[test]
        fn add_8192() {
            let conds = &[
                (MIN_TICK, MIN_SQRT_PRICE_X64),
                (-435444i32, 6469134034u128),
                (-427252i32, 9743708334u128),
                (-419060i32, 14675820844u128),
                (-410868i32, 22104491439u128),
                (-402676i32, 33293438708u128),
                (-394484i32, 50146055794u128),
                (-386292i32, 75529203630u128),
                (-378100i32, 113760903237u128),
                (-369908i32, 171344890234u128),
                (-361716i32, 258076989316u128),
                (-353524i32, 388711518174u128),
                (-345332i32, 585471198968u128),
                (-337140i32, 881827547668u128),
                (-328948i32, 1328194837247u128),
                (-320756i32, 2000506255848u128),
                (-312564i32, 3013131181854u128),
                (-304372i32, 4538330981231u128),
                (-296180i32, 6835563024683u128),
                (-287988i32, 10295617939205u128),
                (-279796i32, 15507098444901u128),
                (-271604i32, 23356548737511u128),
                (-263412i32, 35179267795719u128),
                (-255220i32, 52986462021906u128),
                (-247028i32, 79807378990999u128),
                (-238836i32, 120204623942996u128),
                (-230644i32, 181050321410839u128),
                (-222452i32, 272695157704689u128),
                (-214260i32, 410729174387057u128),
                (-206068i32, 618633847819780u128),
                (-197876i32, 931776609829171u128),
                (-189684i32, 1403427332152165u128),
                (-181492i32, 2113820261052536u128),
                (-173300i32, 3183802961272060u128),
                (-165108i32, 4795394141580141u128),
                (-156916i32, 7222747529549811u128),
                (-148724i32, 10878789174653300u128),
                (-140532i32, 16385461823546584u128),
                (-132340i32, 24679525897647423u128),
                (-124148i32, 37171915268044395u128),
                (-115956i32, 55987756427135721u128),
                (-107764i32, 84327881604718542u128),
                (-99572i32, 127013334159838372u128),
                (-91380i32, 191305494071560812u128),
                (-83188i32, 288141338104768958u128),
                (-74996i32, 433993969319824232u128),
                (-66804i32, 653674917472243071u128),
                (-58612i32, 984554919972768722u128),
                (-50420i32, 1482921196045045371u128),
                (-42228i32, 2233552673466392693u128),
                (-34036i32, 3364142045075557201u128),
                (-25844i32, 5067018044343175492u128),
                (-17652i32, 7631863196526440527u128),
                (-9460i32, 11494992782889323924u128),
                (-1268i32, 17313578044587773368u128),
                (6924i32, 26077440009552195202u128),
                (15116i32, 39277431603132545770u128),
                (23308i32, 59159052145212737538u128),
                (31500i32, 89104437532541615435u128),
                (39692i32, 134207707866954025401u128),
                (47884i32, 202141547039379053500u128),
                (56076i32, 304462431323102511320u128),
                (64268i32, 458576544232723236024u128),
                (72460i32, 690700806685930998863u128),
                (80652i32, 1040322734244533341849u128),
                (88844i32, 1566917804221042780955u128),
                (97036i32, 2360067048777748878333u128),
                (105228i32, 3554696015146416327728u128),
                (113420i32, 5354027448771753053849u128),
                (121612i32, 8064152265076495777509u128),
                (129804i32, 12146099805531775413986u128),
                (137996i32, 18294265241597542985618u128),
                (146188i32, 27554535701863614251349u128),
                (154380i32, 41502209994139943735688u128),
                (162572i32, 62509978503509857430008u128),
                (170764i32, 94151550316501166015374u128),
                (178956i32, 141809590072134153287567u128),
                (187148i32, 213591382922796360386167u128),
                (195340i32, 321707994753150974367081u128),
                (203532i32, 484551541695399563250045u128),
                (211724i32, 729823940929863649029821u128),
                (219916i32, 1099249386124601266815826u128),
                (228108i32, 1655672204115095663735083u128),
                (236300i32, 2493747535437436120135448u128),
                (244492i32, 3756043469863061373001775u128),
                (252684i32, 5657293830678910872509579u128),
                (260876i32, 8520927338416695579743133u128),
                (269068i32, 12834087264981926946395627u128),
                (277260i32, 19330501174743891888009667u128),
                (285452i32, 29115298030295977315653861u128),
                (293644i32, 43853005761718846222391630u128),
                (301836i32, 66050710260162046236327313u128),
                (310028i32, 99484545017898384788354795u128),
                (318220i32, 149842063142622275743464000u128),
                (326412i32, 225689768021737635366423310u128),
                (334604i32, 339930392851198942336359378u128),
                (342796i32, 511997832231547257454131319u128),
                (350988i32, 771163113751212880382552795u128),
                (359180i32, 1161513800592657121378159185u128),
                (367372i32, 1749453889728497108561585311u128),
                (375564i32, 2635000041088204876898305122u128),
                (383756i32, 3968795780957897049549158548u128),
                (391948i32, 5977738028590011050335983803u128),
                (400140i32, 9003575369107728059505649166u128),
                (408332i32, 13561044167458152057771544136u128),
                (416524i32, 20425432272465755407974393642u128),
                (424716i32, 30764466096070844661666573841u128),
                (432908i32, 46336956865884575749971225451u128),
                (441100i32, 69791998498718342082343613614u128),
                (MAX_TICK, MAX_SQRT_PRICE_X64),
            ];
            for (tick, price) in conds {
                assert_eq!(get_sqrt_price_at_tick(*tick), *price);
            }
        }

        #[test]
        fn test_all() {
            for t in MIN_TICK..MAX_TICK {
                get_sqrt_price_at_tick(t);
            }
        }
    }

    mod test_get_tick_at_sqrt_price {
        use super::*;

        #[test]
        fn max_sqrt_price() {
            assert_eq!(get_tick_at_sqrt_price(MAX_SQRT_PRICE_X64), MAX_TICK)
        }

        #[test]
        fn min_sqrt_price() {
            assert_eq!(get_tick_at_sqrt_price(MIN_SQRT_PRICE_X64), MIN_TICK)
        }
    }

    mod fuzz_tests {
        use proptest::prelude::*;

        proptest! {
            #[test]
            fn fuzz_sqrt_price_at_tick(t in MIN_TICK..MAX_TICK) {
                let p1 = get_sqrt_price_at_tick(t);
                let p2 = get_sqrt_price_at_tick(t+1);
                assert!(p2 > p1);
            }

            #[test]
            fn fuzz_tick_at_sqrt_price(p in MIN_SQRT_PRICE_X64..MAX_SQRT_PRICE_X64) {
                let tick = get_tick_at_sqrt_price(p);
                let p_lower = get_sqrt_price_at_tick(tick-1);
                let p_upper = get_sqrt_price_at_tick(tick+1);
                assert!(p_lower < p && p_upper > p);
            }
        }
    }
}