Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - harold

Pages: 1 [2] 3 4 ... 16
Axe / Re: Huffman compression
« on: March 08, 2015, 04:38:06 pm »
You can use whatever order is convenient, it really doesn't matter as long as in the end every length is saved.

Are you using this by the way? In-Place Calculation of Minimum-Redundancy Codes

Also, Deflate uses 15 bits max, so you could probably dial the length down a bit and make some tables smaller. Maybe 14? 13? Using the simplest single-layer decoding would still take a "slightly bigger than would be nice" table though..

Axe / Re: Huffman compression
« on: March 08, 2015, 02:34:26 pm »
It is, but it doesn't need real recursion, it just abuses recursion to push nodes on the stack so it can go back up to a parent. So it can be replaced by a stack of nodes (pop a node, "visit" it, push its two children), or parent pointers (takes more space, also has to know whether a node has been processed).

Axe / Re: Huffman compression
« on: March 08, 2015, 01:28:06 pm »
Just a regular old Pre-Order traversal or whatever. Any order works.

Axe / Re: Huffman compression
« on: March 08, 2015, 01:24:03 pm »
That's fine (but be careful, it can give very long longest symbols, and that's bad for decoding - you can iterate this algorithm with all the frequences divided by 2 (rounding up), that will reduce the skew). You can throw the tree away after extracting the symbol lengths (the patterns are useless, you're using canonical encoding right? so you'd end up reassigning them anyway). You can just traverse the nodes in any order and at every leaf, write the depth into lengths[leaf.symbol].

An other way is using the Package-merge algorithm to immediately generate optimal lengths given that there is some maximum length. Doesn't use trees.

Axe / Re: Huffman compression
« on: March 08, 2015, 01:11:28 pm »
The best decompression techniques all rely on building a table that you index with your current buffer, giving you the first symbol in the buffer and its size. That may be awkward on z80 though, that table can get pretty big (2 to the power however long you allow your longest symbol to be). There are more advanced techniques that use smaller buffers for that, but they tend to rely on other things that are awkward on z80 (such as bitscan). Or nested tables, but they are intrinsically a pain.

I don't even know where this tree search for encoding is coming from, doing it the normal way is much simpler. That table is only as long as your alphabet is big.

Computer Programming / Re: x86 machine code
« on: February 19, 2015, 01:27:16 pm »
Well not really, but there is plenty of information to get started, in the form of assembly tutorials, the Intel manuals (or the AMD manuals if you want), and this handy ModRM table.

Encoding x86 instructions isn't too bad once you know how they work, for example take "add r8, [r10 + 8 * r9 + 8]". This is of the form add r64, rm64, so that'll be REX.W 03 /r. The rm operand needs a SIB byte, so the ModRM and SIB are 44 CA, also REX.B, REX.X and REX.R should be set, and the ofs8 is 8. So in total: 4F 03 44 CA 08

Introduce Yourself! / Re: Hi, I'm Ephraim Becker
« on: February 06, 2015, 05:53:58 am »
I learned assembly as my first language, so it can definitely be done. I won't claim it was easy. But you get used to it.

Fundamentally it is simpler than high level languages, what's harder about it is not getting lost in large pieces of code. But fundamentally, assembly is literally a list of instructions, the way you would write them down for someone to follow, but limited to things a computer can do. High level languages are full of complications such as types, expressions, and weird syntax that you have to learn.

I just looked them up, they were probably derived by someone much smarter than me (but I don't know who)

The first M means the arrivals are determined by a Poisson process, the second M means the service times have an exponential distribution. The 1 means there is 1 server. There are no PDFs or factorials involved under these circumstances, though in general there may be (for example for more than one server, the factorial of the number of servers shows up all over the place - of course in this special case that's just 1).

Actually on second thought I think they're all supposed to be M/M/1, so the formulas are:

Waiting time = arrival_rate / (service_rate * (service_rate - arrival_rate))
Expected queue length = arrival_rate * waiting time

Those questions are then just applying those or solving for some parameter.

It depends on whether the service rate is deterministic or also random, and that's not clear in Q2

Humour and Jokes / Re: Important life algorithms
« on: December 24, 2014, 07:20:13 pm »
Most other languages too, but you can fix it:
Code: [Select]
You're in trouble if you start with zero though.

Humour and Jokes / Re: Important life algorithms
« on: December 24, 2014, 02:46:48 pm »
On a slightly more serious note, the MiniMax algorithm also applies to real life. But in order for it to work, you have to be good at predicting consequences and reactions, and you need an objective function, so it's very hard to ever actually use it.

Introduce Yourself! / Re: Spartan *Spartan braces for peanut overload*
« on: December 14, 2014, 09:19:47 am »
Any plans to learn asm or Axe?

The Axe Parser Project / Re: [AXE] asm codes
« on: December 11, 2014, 01:57:02 pm »
Can you write it in assembly?
Do that, then convert it to hexadecimal machine code.

There are also many available snippets.

Pages: 1 [2] 3 4 ... 16