Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dirty tricks 6502 programmers use

nurpax.github.io

Post reply on HN
Print view View original

51–60 of 63 posts

Re: Dirty tricks 6502 programmers use

#51

Post by userbinator »

saagarjha wrote: post #35
stjo wrote: post #34

Earlier quoted context omitted.

I would say no. 34 bytes is 256^32=7588550360256754183279148073529370729071901715047420004889892225542594864082845696 combinations, and even if you could easily narrow it down to only valid programs you would still need to simulate it, which is way slower than computing a hash.

Only a fraction of those would be reasonable programs, and you can test almost all of them immediately by computing a MD5 hash.

34 bytes is equivalent to bruteforcing a 272-bit key. It's already physically impossible to do that for a 256-bit key even if you ignore everything other than incrementing the key counter itself:

https://pthree.org/2016/06/19/the-physics-of-brute-force/

Re: Dirty tricks 6502 programmers use

#52

Post by joezydeco »

scarface74 wrote: post #43
joezydeco wrote: post #19

Earlier quoted context omitted.

Yeah the moment they introduced a ROM call to optimize the routine, I kind of lost interest.

Why? The memory layout of the text page would have also been c64 specific.

Because the article was titled "dirty 6502 tricks" and not "dirty C64 tricks".

If the article was more about hidden opcodes or instruction set side effects, that's great. But if the key to shaving 8 bytes out of the routine was calling a 120-byte function that's free in the ROM, there's no real trick to 6502 programming being revealed.

It's the equivalent of a blog post titled "I wrote a web server in 3 lines of code!" and the author calls .start() in some imported framework that contains 250,000 lines of code.

Re: Dirty tricks 6502 programmers use

#53

Post by scarface74 »

joezydeco wrote: post #52
scarface74 wrote: post #43

Earlier quoted context omitted.

Why? The memory layout of the text page would have also been c64 specific.

Because the article was titled "dirty 6502 tricks" and not "dirty C64 tricks". If the article was more about hidden opcodes or instruction set side effects, that's great. But if the key to shaving 8 bytes out of the routine was calling a 120-byte function that's free in the ROM, there's no real trick to 6502 programming being revealed. It's the equivalent of a blog post titled "I wrote a web server in 3 lines of code…

True. But in his defense, once you want to put text on the screen, you’re already using implementation defined behavior. Like I said in another reply, the character to memory location mapping is different between for instance the C64 and the Apple //e.

The Apple //e would have had a text scrolling function in ROM.

Re: Dirty tricks 6502 programmers use

#54

Post by tenebrisalietum »

vidarh wrote: post #24
reaperducer wrote: post #7

Earlier quoted context omitted.

title should really be named "Dirty tricks C64 6502 programmers use". In that case, probably Dirty Tricks 6510 Programmers Use would be even better.

While that may be technically correct, the programmer-visibile difference between the MOS 6502 and the MOS 6510 is totally incidental in this case - the 6510 has a a built in 6/8-pin IO port (partially used for bank switching the ROMs in the C64). Unless you touch the IO ports, they should behave identically, down to the cycle timings of instructions and the same behavior of undocumented opcodes. In this case, the re…

A real "dirty trick" is reading the actual RAM in memory locations 0 and 1 on the 6510 (and not the I/O port values).

Re: Dirty tricks 6502 programmers use

#55

Post by rusk »

FartyMcFarter wrote: post #46
saagarjha wrote: post #23

Earlier quoted context omitted.

I wonder if you could brute force a particular solution with that information.

One way to work around that is to allow authors to include comments in the code that gets hashed. (I'm not sure if this particular competition did that)

are you talking about padding it out to provoke a collision?

Remember, that at the end of the day, you still have to have actual working code …

Re: Dirty tricks 6502 programmers use

#56

Post by IcePic »

janekm wrote: post #48
saagarjha wrote: post #35

Earlier quoted context omitted.

Only a fraction of those would be reasonable programs, and you can test almost all of them immediately by computing a MD5 hash.

Or, you could evaluate whether said program draws the crossed lines in an emulator. Might not take that much longer than calculating the hash... That makes this kind of an interesting "Genetic Programming" challenge... The solution space is "only" 29 bytes long...

I don't think that would be this quick either. Since the code might/will mess up zeropage and/or other dataareas in use by the C64 basic, you would have to wipe it to a known state for each test, which almost means "boot up the KERNAL and let it run complete INIT".

Not that even this have to take a long while on a 3GHz computer running full speed, but doing it 2^272 times ...

Re: Dirty tricks 6502 programmers use

#57

Post by FartyMcFarter »

rusk wrote: post #55
FartyMcFarter wrote: post #46

Earlier quoted context omitted.

One way to work around that is to allow authors to include comments in the code that gets hashed. (I'm not sure if this particular competition did that)

are you talking about padding it out to provoke a collision? Remember, that at the end of the day, you still have to have actual working code …

No - what I mean is that if someone is worried that their code will be derived from their published hash by someone doing a brute-force attack, they can prevent (or make much harder) this brute-force attack by having comments in their source code.

I'm assuming here that the hashed string is the source code rather than the machine code.

Re: Dirty tricks 6502 programmers use

#58

Post by saagarjha »

userbinator wrote: post #51
saagarjha wrote: post #35

Earlier quoted context omitted.

Only a fraction of those would be reasonable programs, and you can test almost all of them immediately by computing a MD5 hash.

34 bytes is equivalent to bruteforcing a 272-bit key. It's already physically impossible to do that for a 256-bit key even if you ignore everything other than incrementing the key counter itself: https://pthree.org/2016/06/19/the-physics-of-brute-force/

But as I said, you’re not brute forcing the entire key space because you likely have an idea of at least some of the bits.

Re: Dirty tricks 6502 programmers use

#59

Post by saagarjha »

IcePic wrote: post #56
janekm wrote: post #48

Earlier quoted context omitted.

Or, you could evaluate whether said program draws the crossed lines in an emulator. Might not take that much longer than calculating the hash... That makes this kind of an interesting "Genetic Programming" challenge... The solution space is "only" 29 bytes long...

I don't think that would be this quick either. Since the code might/will mess up zeropage and/or other dataareas in use by the C64 basic, you would have to wipe it to a known state for each test, which almost means "boot up the KERNAL and let it run complete INIT". Not that even this have to take a long while on a 3GHz computer running full speed, but doing it 2^272 times ...

> you would have to wipe it to a known state for each test, which almost means "boot up the KERNAL and let it run complete INIT"

FWIW, if I were actually doing this I’d run it in a emulator and “save” the initial state to restore for the every test.

Re: Dirty tricks 6502 programmers use

#60

Post by rusk »

FartyMcFarter wrote: post #57
rusk wrote: post #55

Earlier quoted context omitted.

are you talking about padding it out to provoke a collision? Remember, that at the end of the day, you still have to have actual working code …

No - what I mean is that if someone is worried that their code will be derived from their published hash by someone doing a brute-force attack, they can prevent (or make much harder) this brute-force attack by having comments in their source code. I'm assuming here that the hashed string is the source code rather than the machine code.

Ahhh - a salt
Post reply on HN