Generating primes (list inside a repeat block)

Index > Macroinstructions > Generating primes (list inside a repeat block)

Author

Thread

RIxRIpt

Joined: 18 Apr 2013
Posts: 50

RIxRIpt 20 Oct 2015, 18:25

Code:

include 'exmacro/print.inc'

fasm_sqrt_result = 0
macro fasm_sqrt x {
    local y
    y = 0
    while x >= 0
        x = x - y
        y = y + 1
        x = x - y
    end while
    fasm_sqrt_result = y - 1
}

n = 256
fasm_sqrt n
n_sqrt = fasm_sqrt_result

primes equ
macro add_prime p {
    match x, primes \{ primes equ primes,p \}
    match  , primes \{ primes equ p \}
}

virtual at 0
    db 1111'1100b
    db 1 + (n_sqrt - 1) / 8 dup 1111'1111b
    repeat n_sqrt + 1
        i = % - 1
        load x byte from i / 8
        if x and (1 shl (i and 7))
            add_prime i
            base = i * i
            limit = 1 + (n_sqrt - base) / i
            if limit > 0
                repeat limit
                    a = base + i * (% - 1)
                    load y byte from a / 8
                    y = y and (not (1 shl (a and 7)))
                    store byte y at a / 8
                end repeat
            end if
        end if
    end repeat
end virtual

macro list_primes [prime] {
    display d=prime, 13, 10
    restore prime
}

list_primes primes

Hello,
I'm trying to generate a list of prime numbers during the compilation. Everything works fine, except one thing - saving a prime number to the list to use it later.

I guess, I'm doing something really wrong, i.e. mixing preprocessor features with assembly.
As I read from docs, `if` and `repeat` statement are parsed on the assembly stage, but `match` is a preprocessor directive. I know there's `rept` directive, and I can use `match` instead of `if`, but `rept` works only with a constant.

So the question is: how can I output a prime number generated in the virtual block, outside the virtual block?

_________________
Привет =3
Admins, please activate my account "RIscRIpt"

Last edited by RIxRIpt on 24 Oct 2015, 11:26; edited 1 time in total

20 Oct 2015, 18:25

l_inc

Joined: 23 Oct 2009
Posts: 881

l_inc 20 Oct 2015, 22:06

RIxRIpt
There are multiple things you could do:

1) Do all the calculations in the preprocessing stage by means of the rept directive. It works with numbers as well as with symbolic constants as long as they expand into numbers.

High memory overhead, slow. Numbers are limited to the signed 32 bit integer range.

2) Generate a list of identifiers during preprocessing and then assign prime values to them during assembly.

Moderate memory overhead, relatively fast.

3) Do all the stuff during the assembly stage only. Generate an array (dd or dq) stored into a labeled virtual addressing space (see the last two paragraphs at the end of the section "Addressing spaces").

Minimal memory overhead, fast. More flexible.

_________________
Faith is a superposition of knowledge and fallacy

20 Oct 2015, 22:06

RIxRIpt

Joined: 18 Apr 2013
Posts: 50

RIxRIpt 24 Oct 2015, 10:45

l_inc, tyvm! I didn't know about labelled virtual addressing space. Here's the final, working result:

Code:

include 'exmacro/print.inc'

fasm_sqrt_result = 0
macro fasm_sqrt n {
    local x, y
    x = n
    y = 0
    while x >= 0
        x = x - y
        y = y + 1
        x = x - y
    end while
    fasm_sqrt_result = y - 1
}

macro generate_primes n {
    local x, y, i, j, slimit, sbase, number_of_primes, virtual_primes, va_offset
    number_of_primes = 0
    virtual at 0
        db 1111'1100b
        db 1 + (n - 1) / 8 dup 1111'1111b
        virtual_primes::
        repeat n + 1
            i = % - 1
            load x byte from i / 8
            if x and (1 shl (i and 7))
                dq i
                number_of_primes = number_of_primes + 1
                sbase = i * i
                slimit = 1 + (n - sbase) / i
                if slimit > 0
                    repeat slimit
                        j = sbase + i * (% - 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 virtual
    va_offset = (n - 1) / 8 + 1 + 1
    repeat number_of_primes
        load q qword from virtual_primes:va_offset + (% - 1) * 8
        dq q
        display d=q, 13, 10
    end repeat
}

fasm_sqrt 1 shl 31
generate_primes fasm_sqrt_result

By the way, is it a bug or feature? I have to add an offset to LVAS, despite the fact the label was defined after some data.

Code:

virtual at 0
        db 1111'1100b
        db 1 + (n - 1) / 8 dup 1111'1111b
        virtual_primes::

Code:

    va_offset = (n - 1) / 8 + 1 + 1
    repeat number_of_primes
        load q qword from virtual_primes:va_offset + (% - 1) * 8

Update: second version, with less `loads` in the main loop:

Code:

macro generate_primes n {
    local x, y, i, j, p, slimit, sbase, virtual_prime_bits
    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
}

24 Oct 2015, 10:45

l_inc

Joined: 23 Oct 2009
Posts: 881

l_inc 24 Oct 2015, 11:30

RIxRIpt

Quote:

By the way, is it a bug or feature? I have to add an offset to LVAS, despite the fact the label was defined after some data.

It's a feature. The addressing space labels refer to the addressing space only, they don't hold any information about the offset inside it. You can therefore define such label at any location of the addressing space, but keep in mind that unlike the normal labels they unfortunately cannot be forward referenced even if the data you access is not forward referenced. I.e. the following won't work:

Code:

outsideOffset dd 1
b_outsideAS::
virtual
    load val dword from f_outsideAS:outsideOffset
end virtual
f_outsideAS::

But it will work if you use b_outsideAS instead.

As for the va_offset you can define it as a normal label to know where to start reading like virtual_primes:: va_offset: .

_________________
Faith is a superposition of knowledge and fallacy

24 Oct 2015, 11:30

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 24 Oct 2015, 11:40

RIxRIpt wrote:

By the way, is it a bug or feature? I have to add an offset to LVAS, despite the fact the label was defined after some data.

The "::" symbol does not label any specific point or address like ":", but it labels the entire addressing space, in this case entire virtual block. It does not matter where inside that block you put "::" label, it always refers to the same thing - the entire virtual block. The "$$" symbol is the base address of current addressing space and it is this address that is the used as base when you refer to that block through "::" label. The "$$" value does not change if you put it before the DBs or after, and analogously the base address for block associated with "::" label stays the same, no matter if you put it before these DBs or after them.

By the way, I like to use various code samples that do not use any x86 instructions, like this one, to test the compatibility of fasm g with fasm 1. So I took your macro and tested it in fasm g (obviously I had to change "{}" to "end macro") - it worked perfectly. Well, of course much slower than in fasm 1, but that's the price of the unified design that fasm g has.

24 Oct 2015, 11:40

RIxRIpt

Joined: 18 Apr 2013
Posts: 50

RIxRIpt 24 Oct 2015, 11:49

Thanks for the explanations. I liked the analogy of :: with $$, makes sense Smile

Quote:

By the way, I like to use various code samples that do not use any x86 instructions, like this one, to test the compatibility of fasm g with fasm 1. So I took your macro and tested it in fasm g (obviously I had to change "{}" to "end macro") - it worked perfectly. Well, of course much slower than in fasm 1, but that's the price of the unified design that fasm g has.

Cool, I'm glad this macro is useful for at least this purpose Very Happy

24 Oct 2015, 11:49

l_inc

Joined: 23 Oct 2009
Posts: 881

l_inc 24 Oct 2015, 11:50

Tomasz Grysztar

Quote:

and it is this address that is the used as base when you refer to that block through "::" label.

The wording is misleading. When referring to data through an addressing space label no base address is added to the expression after the colon.

_________________
Faith is a superposition of knowledge and fallacy

24 Oct 2015, 11:50

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8351
Location: Kraków, Poland

Tomasz Grysztar 24 Oct 2015, 11:59

l_inc wrote:

Tomasz Grysztar

Quote:
and it is this address that is the used as base when you refer to that block through "::" label.

The wording is misleading. When referring to data through an addressing space label no base address is added to the expression after the colon.

Yes, I did phrase this wrongly. The address that you give after the colon is treated as "$$+offset" where "offset" is the position inside the virtual block. And also "$" symbol is always equal to "$$+offset", where "offset" is the position inside the current addressing space, and so every label you define with ":" has this kind of value.

What I did mean there is that you cannot load/store at addresses smaller than that base address, because they would translate to negative offsets.

24 Oct 2015, 11:59

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum