3 ms·

I am the original author of Hex Fiend. Like Tweak, Hex Fiend uses a BTree (actually a B+tree, which also cross-links nodes at the same level, for easy iteration

I am the original author of Hex Fiend. Like Tweak, Hex Fiend uses a BTree (actually a B+tree, which also cross-links nodes at the same level, for easy iteration). Each interior node is annotated with the amount of data contained in its subtree, so it is possible to quickly find data at an offset. I think this is the same as the author's idea. Hex Fiend has an additional trick: it can save files in-place without needing additional disk space. It does this by computing a dependency graph, and then writing chunks in topological order. For example, say you have a 100 byte file, and the user inserts 100 bytes at the beginning. We get a graph: [100, 200) depends on [0, 100) [0, 100) from memory (no dependencies) The topo sort means we'll write [100, 200) first, so its source data is not overwritten. Here is Hex Fiend's B+tree: https://github.com/HexFiend/HexFiend/blob/master/framework/sources/BTree/HFBTree.m https://github.com/HexFiend/HexFiend/blob/master/framework/s...

lifepillar 6y ago
Thank you for making HexFiend, that’s the top hex editor! One thing that I really really like about HexFiend is that scrolling is very fast, yet precise and smooth, no matter the size of the file. Is it based on custom classes? Scrolling in macOS used to be quite ok up to several releases ago. Then it became crappy, especially in some apps (AppleScript Editor comes to my mind).
- ridiculous_fish 6y ago
  Hex Fiend uses native Mac scrollbars, but manages its scroll position itself. In Cocoa speak it uses NSScroller but not NSScrollView.
anyfoo 6y ago
Thanks for making Hex Fiend. It's my go to hex editor, and I use it a lot.
waynesonfire 6y ago
Really interesting stuff. I'm super curious how the Btree data structure is used to optimize this use case. The idea of editing a file is straight forward but the application of a b+tree to this problem for me isn't. Can you describe a bit more how a btree is used here? Do you create a btree of the file data with fixed sized blocks? And then make changes to the btree as the user modifies the file and then flush the btree back to disk? A related question. It's common for filesystems to use btrees... why not just mmap the file?
- anyfoo 6y ago
  If you only mmap the file, how do you handle the case of inserting or deleting bytes in the middle of a large file? Answering that might also help imagining why and how B+Trees are used (the "+" for iteration actually being at least extremely useful, if not important).
- ridiculous_fish 6y ago
  Great questions! A Hex Fiend document is represented in-memory as a list of slices of files and memory buffers. The b+tree is just an optimization on top of the list, and is not written to disk. For example, say the user opens file1, which is 100 bytes. Our document starts off with one slice: (file1, 0, 100) Now the user scrolls to offset 75 and types 30 bytes. This splits the original slice at offset 75, so our new list is: (file1, 0, 75), (memory, 0, 30), (file1, 75, 100) The user may also open file2, copy part of it, and paste it at the end of the document. Now the document references two files: (file1, 0, 75), (memory, 0, 30), (file1, 75, 100), (file2, 200, 300) So there's no real dependence on the original file: a document may reference arbitrarily many files (until it's saved). By organizing the list as a b+tree, it's fast to find the slice at a given byte offset in the document. Hex Fiend does not use mmap because I wanted to support 4+GB files in 32 bit mode. But error handling with mmap is miserable, so I think it is wise to avoid mmap even in 64 bit.
  - anyfoo 6y ago
    I'm surprised you don't mention insertion/deletion for why plain mmap (without chunk lists or trees) does not work... isn't that a deal breaker regardless, or am I missing something? EDIT: Ah, did you just mean why it doesn't use mmap at all, e.g. backing the actual data in the tree?
    - ridiculous_fish 6y ago
      Yep. A simple no-insertion editor could just mmap a file with in-place editing. But you could support insertions by weaving together the mmap'd buffer with other buffers. This is how the suckless vis editor works: https://lists.suckless.org/dev/1409/23497.html https://lists.suckless.org/dev/1409/23497.html The advantage is that your document can be a simple list of (ptr, length) pairs. The price you pay is error handling: mmap reports errors through raising SIGSEGV or SIGBUS, which are very painful to handle properly.
petergeoghegan 6y ago
I am the author of a tool that generates wxHexEditor tags and annotations for Postgres relation files -- pg_hexedit: https://github.com/petergeoghegan/pg_hexedit https://github.com/petergeoghegan/pg_hexedit I've invested quite a lot of effort in it, and it would be nice to have support for multiple hex editors. That was anticipated to some degree: https://github.com/petergeoghegan/pg_hexedit#supporting-other-hex-editors https://github.com/petergeoghegan/pg_hexedit#supporting-othe... I understand why you favor a declarative template format for describing files with tags -- that probably scales really nicely. What I'm doing is pretty grotty, but works surprisingly well in practice. I procedurally generate a description of each file in a shell script, and then open the file in wxHexEditor. I'm generating huge XML files, which is slow, but there are simple workarounds to get acceptable performance. wxHexEditor doesn't support declarative tags. But even if it did I might not want to use them; the on-disk format of PostgreSQL is much more complicated than most file formats, and isn't supposed to be consumed by third party tools. Writing a C program that uses the struct definitions from the server itself makes the complexity quite manageable -- the tool is basically feature complete, even though I haven't spent a huge amount of time on it. That said, it would be great if I could adapt pg_hexedit to a hex editor that had some kind of "best of both worlds" support for tags - tags that can be generated lazily and on-demand, when a portion of the file needs to be drawn or redrawn. This would be easy to adapt to -- Postgres relation files always consist of a series of 8KiB blocks/pages. My tool can easily generate tags for any single block without knowing any special context or having any expensive-to-generate state -- I just need a block number (i.e. an 8KiB-aligned byte offset).
mobilio 6y ago
I just want to say THANK YOU for Hex Fiend!

lifepillar 6y ago

Thank you for making HexFiend, that’s the top hex editor! One thing that I really really like about HexFiend is that scrolling is very fast, yet precise and smooth, no matter the size of the file. Is it based on custom classes? Scrolling in macOS used to be quite ok up to several releases ago. Then it became crappy, especially in some apps (AppleScript Editor comes to my mind).

ridiculous_fish 6y ago
Hex Fiend uses native Mac scrollbars, but manages its scroll position itself. In Cocoa speak it uses NSScroller but not NSScrollView.

anyfoo 6y ago

Thanks for making Hex Fiend. It's my go to hex editor, and I use it a lot.

waynesonfire 6y ago

Really interesting stuff. I'm super curious how the Btree data structure is used to optimize this use case. The idea of editing a file is straight forward but the application of a b+tree to this problem for me isn't. Can you describe a bit more how a btree is used here? Do you create a btree of the file data with fixed sized blocks? And then make changes to the btree as the user modifies the file and then flush the btree back to disk? A related question. It's common for filesystems to use btrees... why not just mmap the file?

anyfoo 6y ago
If you only mmap the file, how do you handle the case of inserting or deleting bytes in the middle of a large file? Answering that might also help imagining why and how B+Trees are used (the "+" for iteration actually being at least extremely useful, if not important).
ridiculous_fish 6y ago
Great questions! A Hex Fiend document is represented in-memory as a list of slices of files and memory buffers. The b+tree is just an optimization on top of the list, and is not written to disk. For example, say the user opens file1, which is 100 bytes. Our document starts off with one slice: (file1, 0, 100) Now the user scrolls to offset 75 and types 30 bytes. This splits the original slice at offset 75, so our new list is: (file1, 0, 75), (memory, 0, 30), (file1, 75, 100) The user may also open file2, copy part of it, and paste it at the end of the document. Now the document references two files: (file1, 0, 75), (memory, 0, 30), (file1, 75, 100), (file2, 200, 300) So there's no real dependence on the original file: a document may reference arbitrarily many files (until it's saved). By organizing the list as a b+tree, it's fast to find the slice at a given byte offset in the document. Hex Fiend does not use mmap because I wanted to support 4+GB files in 32 bit mode. But error handling with mmap is miserable, so I think it is wise to avoid mmap even in 64 bit.
- anyfoo 6y ago
  I'm surprised you don't mention insertion/deletion for why plain mmap (without chunk lists or trees) does not work... isn't that a deal breaker regardless, or am I missing something? EDIT: Ah, did you just mean why it doesn't use mmap at all, e.g. backing the actual data in the tree?
  - ridiculous_fish 6y ago
    Yep. A simple no-insertion editor could just mmap a file with in-place editing. But you could support insertions by weaving together the mmap'd buffer with other buffers. This is how the suckless vis editor works: https://lists.suckless.org/dev/1409/23497.html https://lists.suckless.org/dev/1409/23497.html The advantage is that your document can be a simple list of (ptr, length) pairs. The price you pay is error handling: mmap reports errors through raising SIGSEGV or SIGBUS, which are very painful to handle properly.

petergeoghegan 6y ago

I am the author of a tool that generates wxHexEditor tags and annotations for Postgres relation files -- pg_hexedit: https://github.com/petergeoghegan/pg_hexedit https://github.com/petergeoghegan/pg_hexedit I've invested quite a lot of effort in it, and it would be nice to have support for multiple hex editors. That was anticipated to some degree: https://github.com/petergeoghegan/pg_hexedit#supporting-other-hex-editors https://github.com/petergeoghegan/pg_hexedit#supporting-othe... I understand why you favor a declarative template format for describing files with tags -- that probably scales really nicely. What I'm doing is pretty grotty, but works surprisingly well in practice. I procedurally generate a description of each file in a shell script, and then open the file in wxHexEditor. I'm generating huge XML files, which is slow, but there are simple workarounds to get acceptable performance. wxHexEditor doesn't support declarative tags. But even if it did I might not want to use them; the on-disk format of PostgreSQL is much more complicated than most file formats, and isn't supposed to be consumed by third party tools. Writing a C program that uses the struct definitions from the server itself makes the complexity quite manageable -- the tool is basically feature complete, even though I haven't spent a huge amount of time on it. That said, it would be great if I could adapt pg_hexedit to a hex editor that had some kind of "best of both worlds" support for tags - tags that can be generated lazily and on-demand, when a portion of the file needs to be drawn or redrawn. This would be easy to adapt to -- Postgres relation files always consist of a series of 8KiB blocks/pages. My tool can easily generate tags for any single block without knowing any special context or having any expensive-to-generate state -- I just need a block number (i.e. an 8KiB-aligned byte offset).

mobilio 6y ago

I just want to say THANK YOU for Hex Fiend!