How to find max non-repeating element in array without conditional jumps, using Fast-Strings?

Question

I'm solving online test, that our teacher has come up with.

The task is not too hard itself:

EAX contains a pointer to an unknown size array of shorts terminated with 0.
Write a code that finds maximum of all elements that !does not repeat!, which goes to BX register. 
EAX and contents of the array must remain unchanged.
For example, the array:
    15,900,900,8,96,108,108,96,0
will have 15 in BX.

If an element with properties listed above, return 0;

But the problem is in the instruction set we have to use:

the only commands we have are MOV, PUSH, POP, INC, DEC, NEG, LOOP, STD, CLD, REP* MOVS*, CMPS*, SCAS*, LODS* and STOS*!

No conditional jumps allowed, no functions.

With those instructions I'm completely lost.

I tried searching the end of the array using

    cld
    mov edi, eax   
    mov ecx, -1           
    mov  al, 0        
    repne  scasb
    inc ecx   
    inc ecx    
    neg    ecx

and I'm thinking of repeating loop rep cmps with decrementing array length I found in previous state. But can't come up with a solution that works.

I'm using Intel x86 assembly NASM variation, but any will do.

*No conditional jumps allowed* - `loop` is a conditional jump. You can use `inc ecx` / `loop target` as an equivalent for jump if ECX != 0. Like the opposite of `jecxz`. Or of course the more usual use-case of using it as the bottom of a `do{}while(--ecx)` loop. You can't use this to branch on any flag conditions, though, unless you're allowed to use `loope` or `loopne`. — Peter Cordes, Apr 06 '20 at 19:27
`mov` on its own it Turing-complete, and https://github.com/xoreaxeaxeax/movfuscator can compile C into code only using `mov`. So it's definitely doable if you're willing to make the code nasty enough! But probably there's a more reasonable solution. It's not immediately obvious, though. — Peter Cordes, Apr 06 '20 at 19:32
That's weird; Fast Strings and [ERMSB](https://stackoverflow.com/questions/43343231/enhanced-rep-movsb-for-memcpy) only work for `rep movsb` / `rep stosb`, not any of the conditional repeat operations like `repe/ne scas` or `repe/ne cmps`. Those are still slow even on latest-gen CPUs like Ice Lake and Zen2, like 1 memory access per clock, not using wider SIMD ops in microcode. https://www.agner.org/optimize/instruction_tables.pdf has timings up to Skylake and Zen1 showing startup overhead and clocks per count. — Peter Cordes, Apr 06 '20 at 19:41
As Peter said, the `loop` instruction can be used for a jump if (not) zero conditional. You have already found a way to get the array length. You should have no problem iterating all the items and using `repne scas` to see if they are duplicated (you can set the item to zero temporarily). The only thing left is to find the biggest one, which can be done for example by subtracting 1 from both numbers (the current max and the candidate) in a loop and see which gets to zero first. — Jester, Apr 06 '20 at 19:46

How to find max non-repeating element in array without conditional jumps, using Fast-Strings?

0 Answers0