Bit combinations

[smertniki]

Hello guys,

I'm looking for a code which would generate all possible combinations of a given range and a given size represented by bitsets (left-to-right order), something like this:
Let's take a short range: Combinations(5,2) = 10

01 02 - 11000000000000000000000000000000
01 03 - 10100000000000000000000000000000
01 04 - 10010000000000000000000000000000
01 05 - 10001000000000000000000000000000
02 03 - 01100000000000000000000000000000
02 04 - 01010000000000000000000000000000
02 05 - 01000100000000000000000000000000
03 04 - 00110000000000000000000000000000
03 05 - 00101000000000000000000000000000
04 05 - 00011000000000000000000000000000

Is it possible to be done by simple bit manipulations?

Regards

[dedndave]

it could probably be faster, but this will work

        mov     ebx,80000000h

loop00: mov     edx,ebx
        jmp short loop02

loop01: mov     eax,ebx
        or      eax,edx
                          ;result is in EAX - store it or whatever

loop02: shr     edx,1
        jnz     loop01

        shr     ebx,1
        jnz     loop00

[smertniki]

What fast reply  :bg

Thanks a lot dedndave!
I'm an asm noob and I had no idea of how to do it...

Thanks a lot, really  :U

[dedndave]

glad i could help
i wish all the questions were so hard   :P

[dedndave]

i re-read your first post
the first time i read it, i saw "all possible combinations" and went to town - lol
by adding a few lines, you can limit the range (5 bit limit value shown)

        mov     ecx,04000000h ;adjust this value to limit the range
        mov     ebx,80000000h

loop00: mov     edx,ebx
        jmp short loop02

loop01: mov     eax,ebx
        or      eax,edx
                          ;result is in EAX - store it or whatever

loop02: shr     edx,1
        cmp     edx,ecx
        jnz     loop01

        shr     ebx,1
        cmp     ebx,ecx
        jnz     loop00

[Farabi]

What fast reply  :bg

Thanks a lot dedndave!
I'm an asm noob and I had no idea of how to do it...

Thanks a lot, really  :U

I wish I still had the same strenght just like when I was young, I think I will be the winner (Oh Im 25 now) *cough*  :green

[dedndave]

Happy Birthday, Onan !!!   

[Farabi]

Happy Birthday, Onan !!!   

Not yet dave. I will be 26 on 26th february :mrgreen

[dedndave]

i will be 55 on the 25th of march   :P
my wife just turned 36   :bg

[oex]

Not yet dave. I will be 26 on 26th february :mrgreen

3 more days and you could have been 6?

[dedndave]

something to do with the modulus function - lol
he would still feel 25   :lol
which seems nice to me
i was having a lot of fun when i was 25

[smertniki]

Farabi,

The second place is not bad, I'm 30 and probably I would take more than a year to develope that code by myself (just started with asm 3 weeks ago)  :lol

Dave,

Thanks for the code correction, but as you must imagine, I still have much more questions than their answers  :P

For example, tell me if the complete code should look like this please:

Code Select Expand


.486
.MODEL FLAT, STDCALL
.DATA
.CODE

start:
        mov     ecx,04000000h ;adjust this value to limit the range
        mov     ebx,80000000h

loop00: mov     edx,ebx
        jmp short loop02

loop01: mov     eax,ebx
        or      eax,edx
                          ;result is in EAX - store it or whatever

loop02: shr     edx,1
        cmp     edx,ecx
        jnz     loop01

        shr     ebx,1
        cmp     ebx,ecx
        jnz     loop00
end start



I could compile it, but seems that I entered in a infinite loop, should I have to put the "ret" instruction somewhere?

- the jmp instruction is the inconditional jump, but what means the "short" instruction??
- the first value to be processed is the hex 80000000h right? which means 10000000000000000000000000000000 in binary value, then we shr it, now the EDX would be 01000000000000000000000000000000 or 11000000000000000000000000000000?
- and the last question... how can I display on the screen the value of the EAX containing the final results inside the loop01?

Please don't pay attention if I'm asking silly questions, I just need to understand what's going on inside the code  :toothy

Thanks once again
Regards,

[dedndave]

well - first thing you need to do is to decide what you want to do with the values generated
you may want to place them in an array or in a file or something

the "short" just tells the assembler that it is a 2-byte JMP instruction
short JMP's can only reach 128 bytes
if i were jumping to a previous label, i would not have to tell the assembler
but, because it is a forward reference, the assembler may not know what size JMP instruction to use
that may be unnecessary with newer versions of MASM - it is just an old habit - lol

every program needs to have a termination call
for 32-bit windows, it is usually a call to the ExitProcess API function
the masm32 macro library provides a simple "exit" macro to save some typing, or you can INVOKE the ExitProcess API call
that function is part of the kernel32.dll, so you have to include that, too
you can include that, and a few other items by simply referencing the masm32\include\masm32rt.inc file
you should take a look inside that file - you will see that it also takes care of these lines for you

.486
.MODEL FLAT, STDCALL

to display values as binary strings, you can use the masm32 library dw2bin_ex function
again, the masm32 macro library provides a "PRINT" macro
i think it uses the WriteFile API function to display strings on the console

- the first value to be processed is the hex 80000000h right? which means 10000000000000000000000000000000 in binary value, then we shr it, now the EDX would be 01000000000000000000000000000000 or 11000000000000000000000000000000?

the first value in EBX is 8000000h
we place a copy of that into EDX and SHR,1 - that gives you 40000000h
when we OR EAX,EDX, we get 0C0000000h, or 1100000000000000b

attached is a small program with the source code you can use as an example file
it was assembled with command lines like these:

ml /Sn /c /coff bits.asm
Link /SUBSYSTEM:CONSOLE /OPT:NOREF bits.obj

[smertniki]

Dave,

Perfect, I compiled following your instructions and the program worked perfectly :]

well - first thing you need to do is to decide what you want to do with the values generated
you may want to place them in an array or in a file or something

Yes, in fact I'm plainning to store all combinations in an array, and after a loooong processement (will explain you what's about later), I will need to write them back in a file, but this time converted to number's combinations, which would be made by another function - the 11000000000000000000000000000000 bitstring would be written back as "01 02" in a text file.

But first at all I will look further at your code, modify the ranges to bigger values and to get more familiar with the asm codes, the libraries, etc... before my next code steps.
I'm forcing my mind to "think in low level" after years of high level coding :lol

Dave, thanks a looooot! you saved me one year of hard work in a matter of minutes  :bg

Regards,

[vanjast]

i will be 55 on the 25th of march   :P
my wife just turned 36   :bg

Cradle snatcher... :bg