C program to generate Seed programs from statically defined Befunge code
[Is] there was a better way to do this that would lead to the same or better optimisation.


Yes: don't hardcode stuff the compiler can't do any optimizations about and that makes your program a pain to use. (And an eye-sore because of all those ALL_CAPS_MACROS everywhere.)

Hardcoding the Befunge program gives the compiler next to no useful information. All you're doing with it is comparing it with random data that the compiler can't reason about. (And you're doing that after modifying the string at runtime anyway - the compiler might see through this, but you're adding a tough layer there.)

The hardcoded length could potentially be used to control the amount of loop unrolling in the main loop that the compiler will attempt/choose, but I won't believe that has a significant impact until I see an actual benchmark.

Using char for the loop variables rather than the plain old int won't buy you anything, except the obfuscation you got through that macro - not desirable. Smaller doesn't always mean faster - you might actually incur a performance loss here compared to using a plain int.

What might give the compiler an advantage is having the RNG functions bodies visible when it compiles your main loop - that's the only "computationally expensive" step in your code. But you've put them in a different translation unit, so you've prevented inlining unless you use some form of whole-program optimization/link-time optimization.

So, if I were you, I would first keep this program as it is, and measure its performance on known input(s).

Then start a new one without any of those macros:


read the parameters from command line arguments
move the actual processing code to a function that takes those arguments and returns a seed if found 


At this step, again, measure the performance. If there's a measurable difference either way, try to figure out why. Once you have the why, you can look further at what needs to be done to take advantage (or reject) that difference.

Then you can try again after move the relevant RNG functions into the main file.

Then you can check out your compiler's profile-guided optimization mode if it has it, and see if that changes things.

Measure, rinse, repeat.