Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Better minifier #2

Closed
Rudxain opened this issue Oct 3, 2022 · 9 comments · May be fixed by #3
Closed

Better minifier #2

Rudxain opened this issue Oct 3, 2022 · 9 comments · May be fixed by #3

Comments

@Rudxain
Copy link

Rudxain commented Oct 3, 2022 •
edited
Loading

I want to open a PR to improve the minifier, but I'll need to learn more Golang (my main langs are Rust and JS). I suggest the following optimizations:

  1. Return an empty string if the input doesn't contain . . No, this is unsafe! Infinite loops aren't "output", but still count as "behavior". Link to commit that removed the bug. Instead, remove all ops after last ., only if . isn't followed by ] or , anywhere.
  2. Remove chunks of 256 consecutive + or - (because of mod 256 wrap-around)
  3. Remove mutual-cancel opcodes (+ or - followed by its opposite, same for < and >)
  4. Replace excessive + or - if an equivalent sequence of opposite op does the same thing (replace 129 (or more) by a smaller sequence, exploiting mod 256). For example, if we add 255 times (+ * 0xff), it does the same as subtract once (-).
  5. Replace odd-count cell-reset loops by [-] and even-count by [--] (this exploits mod 2^n arithmetic)
  6. Remove useless arithmetic if reset is found: +++[-] -> [-]
  7. Zero-loop removal. If there are loops before the 1st cell-mutation happens, then all can be removed.
  8. Loop followed by loop: Example [.-.]...[foobar] can be turned into [.-.].... The 1st loop can contain arbitrary code, iff the opcodes between both loops are dots (or no-op). This can be extended indefinitely [foo][foo][foo][foo][foo] -> [foo]
  9. Increase compression ratio by replacing [-] by [+] and vice-versa (frequency analysis for "compressor-friendly" output)
  10. Use a multiplicative algorithm to reduce + and -. This is very hard to implement (halting problem), so I won't do it. It's hard because it requires knowing the exact value of adjacent cells, to safely use them as temporary registers. Example >++++++++++++< -> +++[->++++<] (add 12 to M1 while M0 is 0). If done wrong, it can increase the size of output, >++< -> ++[->+<], so it's another reason to avoid that risk.
@Rudxain
Copy link
Author

Rudxain commented Oct 3, 2022

Wait I have an idea. I can write the full algorithm in TypeScript, then you manually transpile it to Go. What do you think?

@baris-inandi
Copy link
Owner

Thank you for your comments, I'm kinda busy right now, will definitely look into this tomorrow.

@baris-inandi
Copy link
Owner

Hey @Rudxain, just read your comments, took a look at the brnfckr repo and read the linked stackexchange page. Seems like all solutions you mentioned can be implemented. To start off the feature, a reasonable approach would be adding the optimizations to /bffmt/minify.go under func MinifyFile:

https://github.com/baris-inandi/brainfuck-go/blob/c658055bb9ab7b203579b548bf2a4c33fdae3081/bffmt/minify.go#L9

https://github.com/baris-inandi/brainfuck-go/blob/c658055bb9ab7b203579b548bf2a4c33fdae3081/bffmt/minify.go#L11

and we can wrap this line with a minify(string) function:

 minified := minify(readcode.ReadBrainfuck(f))

This function (and readcode.ReadBrainfuck(f) for that matter) currently only removes all non-brainfuck characters (this minification essentially removes newlines and comments so it won't deal with bad code logic that can be fixed). We can start working on an improved minifier anytime.

PS
If you already know Rust and JS, a transition to Go should be quite easy. Manually transpiling TS code might take some time so it would be great if you could consider Go for implementing the improved minifier. If you have a Go-related question I would be happy to help. LMK what you think about that.

@Rudxain
Copy link
Author

Rudxain commented Oct 8, 2022

Thank you for the info! I've been considering learning some Go, and I could use the official VSCode Golang extension for faster development. So that's fine for me! But it'll take some time, please be patient (I'm slow)

@baris-inandi
Copy link
Owner

baris-inandi commented Oct 8, 2022 •
edited
Loading

Great, make sure you open a pull request when you're ready and keep me updated

@Rudxain
Copy link
Author

Rudxain commented Oct 8, 2022

Ok 👍

@Rudxain
Copy link
Author

Rudxain commented Oct 10, 2022 •
edited
Loading

VSCode says "Error: there is no registered task type 'cppbuild'. Did you miss installing an extension that provides a corresponding task provider?". It seems .vscode/tasks.json is the file that defines that task. Can that error be safely ignored?

@Rudxain Rudxain mentioned this issue Oct 11, 2022
Draft
8 tasks
@baris-inandi
Copy link
Owner

VSCode says "Error: there is no registered task type 'cppbuild'. Did you miss installing an extension that provides a corresponding task provider?". It seems .vscode/tasks.json is the file that defines that task. Can that error be safely ignored?

Yeah, tasks.json wasn't supposed to be there anyways, we can remove it

@baris-inandi
Copy link
Owner

#3

@baris-inandi baris-inandi mentioned this issue Apr 21, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

enhance minifier Rudxain/bfgo
2 participants
@baris-inandi @Rudxain