;l_inc's print macro, can be found on the forum
include 'exmacro/print.inc'

;Taken from http://www.codecodex.com/wiki/Calculate_an_integer_square_root
fasm_sqrt_result = 0
macro fasm_sqrt n {
    local root, rem, place
    root = 0
    rem = n
    place = 0x4000000000000000
    while place > rem
        place = place shr 2
    end while
    while place
        if rem >= root + place
            rem = rem - root - place
            root = root + place shl 1
        end if
        root = root shr 1
        place = place shr 2
    end while
    fasm_sqrt_result = root
    display 'ISQRT of ', d=n, ' is ', d=root, 13, 10
}

;Generating prime numbers up to `N`, using Sieve of Eratosthenes
;https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;Thanks to l_inc [ http://board.flatassembler.net/topic.php?p=184093#184093 ]
macro generate_primes n {
    local x, y, i, j, p, slimit, sbase, virtual_prime_bits
    display 'Primes, up to: ', d=n, 13, 10
    virtual at 0
        virtual_prime_bits::
        ; 0, 1 - not primes
        ; 2, .. - probrably primes
        db 1111'1100b
        db 1 + (n - 1) / 8 dup 1111'1111b
        repeat (n + 1) / 8 + 1
            i = % - 1
            load x byte from i
            repeat 8
                j = % - 1
                p = i * 8 + j
                if p > n
                    break
                end if
                if x and (1 shl j)
                    sbase = p * p
                    slimit = 1 + (n - sbase) / p
                    if slimit > 0
                        repeat slimit
                            j = sbase + p * (% - 1)
                            load y byte from j / 8
                            y = y and (not (1 shl (j and 7)))
                            store byte y at j / 8
                        end repeat
                    end if
                end if
            end repeat
        end repeat
    end virtual
    repeat (n + 1) / 8 + 1
        i = % - 1
        load x byte from virtual_prime_bits:i
        repeat 8
            j = % - 1
            if x and (1 shl j)
                p = i * 8 + j
                if p > n
                    break
                end if
                dq p
                display d=p, 13, 10
            end if
        end repeat
    end repeat
}

;Binary search of value with specific type in a specific region [left; right) - right bound not included
;Searches for the left most value, which is equal to `value`
;Returns (sets bisearch_result) address of first value, which is greater or equal to `value`
macro bisearch value, type, left, right {
    local x, l, m, r, base
    display 'Binary search:', 13, 10
    display 'l', 9, 'm', 9, 'r', 9, 'x', 13, 10
    if type eq byte
        size = 1
    else if type eq word
        size = 2
    else if type eq dword
        size = 4
    else if type eq qword
        size = 8
    else
        display 'Invalid type: `', `type, 13, 10
        err
    end if
    l = 0
    r = (right - left - 1) / size
    while l <= r
        m = (l + r) shr 1
        load x type from left + m * size
        display d=l, 9, d=m, 9, d=r, 9, d=x, 13, 10
        if value <= x
            r = m - 1
        else
            l = m + 1
        end if
    end while
    bisearch_result = left + l * size
}

;Usage
Primes:
    fasm_sqrt 1 shl 20
    generate_primes fasm_sqrt_result
EndPrimes:

x = 444
bisearch_result = -1
bisearch x, qword, Primes, EndPrimes

load p qword from bisearch_result
display 'First prime, which is >= ', d=x, ': ', d=p, 13, 10