::::: : the wood : davidrobins.net

My name is David Robins: Christian, lead developer (resume), writer, photographer, runner, libertarian (voluntaryist), and student.

This is also my son David Geoffrey Robins' site.

Lothlórien decommissioned

News, Technical ·Wednesday December 23, 2009 @ 14:24 EST (link)

The machine known for a tile as Lothlórien has been decommissioned. It had been sitting in my office for a while—last login was in fact last Christmas! I verified that I had all the data off it that I needed (it was only a desktop box with most data shared from other machines anyway). It was a Pentium II 400Mhz (!) with a 10 Gb primary HD and a 60 Gb secondary (I also got rid of another 60 Gb drive with the machine). (Hard to believe even a few years back that a 60 Gb drive would be next to worthless… but I suppose not really given Moore's law and such things.) I believe I had it since school—I'm pretty sure I had it when I was on co-op in Toronto, but probably bought it in Waterloo, at a small computer store there. It was of course running (Gentoo) Linux (2.6.20), although earlier on it was a server machine and never had a GUI, until replaced in that capacity and KDE packages were installed so Honey could used it for web browsing and mail.

It served well and will be missed. It is survived by rivendell, cirith-ungol, cair-paravel, and khazad-dum. Requisceat in pace.

Books finished: Trading To Win, Playing For Pizza.

DVDs finished: M*A*S*H: Season Eleven.

Freedom and the environment

Political, Law ·Saturday December 19, 2009 @ 07:04 EST (link)

I asked a "global warming alarmist" former colleague for a book to read that was the sine qua non to convince me of the imminent danger of global warming, and the need to use force to make people pay to reduce or reverse it. He recommended I read chapters 11-12 of Carl Sagan's Billions and Billions, which I did. Unfortunately (to some), I have not now seen the light and dedicated my life to gunning down SUV drivers to save the planet; but here are my impressions of the work.

Chapter 11 starts with some basic definitions of fossil fuels, how their burning causes the reaction C + O2 → CO2, and this carbon dioxide creates a "blanket" in the sky which allows sunlight through but keeps radiated infrared light in, raising the temperature of the earth. He also notes that such a blanket is necessary to an extent, since the temperature with no such buffer would be -20°C (with it, it's 13°C). But then the first big red herring is thrown out: Look at Venus; it should be a pleasant holiday planet, but because of global warming its temperature is 490°C! Ummm… where to start with the holes in such an attempted parallel? Sagan ought to know better; we may certainly presume malice rather than stupidity. Then comes the fact that during the entire twentieth century, the burning of fossil fuels is only claimed to have increased the average temperature of the earth by a few tenths of a °C. Alarm! Wake the neighbors! Not exactly; and that's even supposing that it wasn't caused or influenced by other events. Many events and predictions are then listed, but with the caveat that:
None of these trends by itself is compelling proof that the activities of our civilization rather than natural variability is responsible. … Balance all the positive and all the negative feedbacks and where do you end up? The answer is: Nobody is absolutely sure.
Which is a refreshingly honest statement from such an evangelist.

Now, I'm not going so far as to say there isn't global warming, but if this book is supposed to be the shocker packed with facts to convince a disinterested observer, it falls flat on its face. And perhaps you want to preach a better book; Billions and Billions isn't the true Scotsman; we've come farther in the 12 years since it was published, etc.; I'm willing to read more, but other suggestions are going to be put well down the priority list since this was such a disappointment and there are more sagacious authors on my list that I'd rather read. And if Pascal's original wager isn't enough to cause the heathen to turn to God from idols, his version certainly isn't enough to turn individuals from freedom to a green enslavement.

The second chapter, 12, "Escape from ambush", contains Sagan's suggestions to help fix the problem. It is true as he points out that politicians do not easily look 20-60 years into the future, not only beyond their term of office but beyond their lifetimes. He buys into the idea of taxation as a solution, citing a 1995 Gallup poll that said that "[m]ost would acquiesce to increased taxes if earmarked for environmental protection", as if that justified coercing the rest. There's a lot of "hurry, hurry"—we must do things now emphasis; voluntary action is out of the question; the political power that comes from the barrel of a gun is required!

His comparison of environmental guards to building safeties into skyscrapers and bridges is specious; for the latter, if safeties are not built in then the eventual inevitable failures will bankrupt the builder and he may be found criminally liable; rational self-interest, outside of any law, is all that is needed to cause such safeties to be built. But Sagan says that builders guard against "implausible contingencies", which is not true. Builders in level prairie states do not build the same way as builders in earthquake zones; to do so would be foolish waste. Can rational self-interest also motivate individuals to pay for environmental safeguards? Certainly, if damages can be shown. The harm to one person may be slight, but class action suits have always been used to bring such actions forward. If it can be shown that a company's emissions are causing harm, they can be made to pay damages and penalties (see, e.g., Erin Brokovich). This is how the free market handles environmental damage: let the accuser show harm—the infringement of rights—and the state may legitimately use counter-force to require you to make things right (clean up the mess), and pay damages and losses (including wasted time), just as if the accused had walked up to someone and punched them in the face. If no harm can be shown, the state has no right to impose draconian and irrational penalties, or even any penalties at all. And of course, such payments will tend to balance out: costs of environmental harm will be passed to consumers, so the only people making any profit in the end would be Amish farmers, who as a rule aren't extremely litigious anyway.

I do agree with his economic analysis of the cost of oil, which should as he says include the military adventurism that keeps the price low for American consumers. Why should someone that bicycles to work (and buys local organically grown vegetables, etc.) have to pay the same amount of taxes for "defense" (read: offense) as someone that commutes on hour a day each way? All subsidies are unjustifiable force. I even think his suggestion of adopting a tradition of planting trees at Christmas and birthdays and other events is a nice idea (although his justification beyond their CO2 removal value is risible).

He does throw out as a sop, "Perhaps these alternatives can be quickly developed in a real free-market economy"; it's true that if good precedents are set for pollution causing quantifiable harm, there will be a great demand for any technology that can reduce the environmental impact of industrial processes, automobile engines, etc., so the "perhaps" should be changed to an emphatic, "Definitely!"

Since, as he so elegantly puts it, "CO2 molecules, being brainless, are unable to understand the profound idea of national sovereignty. … If they're produced in one place, they can wind up in any other place.", the idea of showing harm in the courts can be taken international, and nations can sue producers across borders for damages caused them over what they produce. Certainly such calculations won't be easy, but there are clearly a lot of climate scientists out there with a lot of time on their hands; this will give them something useful to do and keep them out of mischief.

While it is reasonable for people to pay for quantifiable damages they cause, it is an immoral initiation of force to rob people (via taxes, levies, subsidies, regulation, or otherwise) to support such things as cleanup, product bans, or payments to developing nations to induce them to change their behavior, just as it would be immoral to require citizens to provide monetary support for any other religion. Cleanup need only be done by those proven to have caused particular harm, but wise observers will see that such infringements cost more than they benefit, and refrain and limit themselves in the environmental damage they do. The rest may be done by the voluntary associations that so impressed De Tocqueville when he came to America; but it is an absolute requirement for freedom that religion—the only label for governmental diktats that do not protect rights—never come from the barrel of a gun.

When is force justified?

Political, Law ·Friday December 18, 2009 @ 04:52 EST (link)

When may one use force? To secure rights.

In the liberty traditions (classical liberalism, libertarianism, objectivism), an action does not acquire morality because it is done by a group, no matter how that group was formed, even if it calls itself "government" and claims to be above the laws of man and nature. So although initially I thought I would have to clarify that I was considering group, even government action, in fact there is no distinction in terms of the question.

What are rights? Let's start with what they are not: rights do not require others to do work to provide them; they cannot exist at the expense of others: there is no right to enslave. (Sometimes the distinction is made between negative and positive rights; I will use the terms rights and privileges.) Rights can only require others to abstain from acting: to not stop me from speaking, to not trespass on my property, to not commit violence against me. The fundamental rights are to personal physical security and to security of one's voluntarily-acquired property (a thief has no right to security of his ill-gotten gains); one could even frame this as Rand's one fundamental right, either to one's own self (and by extension property), or, rephrasing, to property, beginning with self-ownership.

Privileges are too often claimed as rights. For example, Franklin D. Roosevelt's "Economic bill of rights" including such absurdities as the right to a job, a right to food and clothing, for farmers to to sell food at a certain price, to a home, to medical care, to education. For all of these, one naturally asks "Who will provide it?" The list clearly is not talking about voluntary contractual associations: for then it would be foolish to describe these privileges as rights, since they must depend upon mutual agreement. For a job such agreement is between employer and employee, and contains such terms as the work performed and compensation provided in return. No, in this case it would require an employer who does not want to hire someone to hire him, or to keep him employed against his will, or to pay him more than he is worth; all of these things are clear violation of his right of association, of private property (who he allows on it, who he gives it to); they are unjust takings, i.e., robbery and theft. And indeed, the "New Deal" did all these things (see, e.g., Schlaes' The Forgotten Man, or Folsom's New Deal or Raw Deal?). Going down the list, we see outright theft in the alleged "right" to have particular goods; price-fixing (which in practice involved massive destruction of salable goods), to the hurt of the consumers without political leverage; and enslavement of those forced by a tyrannical government to work but not receive the just fruits of their labor.

Clearly, physical self-defense is the first and most obvious justification for use of force; ideally commensurate with the force initiated against one; if there is an option, one should prefer flight, except on one's home ground, where all possible force may legitimately be brought to bear against an intruder and attacker. In the aggregate, a nation may also defend itself from aggression. Such defense secures one's right to physical security (you own yourself exclusively). By extension, one may defend others with their consent.

But nations fight other nations, for other reasons, sometimes even legitimately. (One must take an aside to consider what is a nation? When was the United States of America a nation? From the time a group declared it so. Does this mean that I can declare me and my house an independent nation? Yes: it is my property by dint of voluntary purchase and by residence; but I would face too many logistical difficulties to make that viable; for example, I would be surrounded on all sides by those obliged neither to allow me passage nor transact with me.)

The so-called American Civil War, or War Between the States, or Southern War for Independence, is whitewashed in the histories to associate it with freeing the slaves, but contemplation of the events thereof will indicate that that was merely fortunate happenstance and the war was fought, as usual, for money, land, and power. But let us suppose it was fought to free the slaves; then was it a legitimate war? Referring back to our thesis, we must answer yes; but that certainly doesn't make every act committed during such a war legitimate. It is reasonable to undo the suppression of rights by freeing the slaves; it is not reasonable to suppress speech and assembly rights (or even habeas corpus), or to murder, rape, pillage and burn noncombatants. But as fought, with it expressly declared by many including President Lincoln himself that the war was not started with any goal of freeing slaves, it was unjust initiation of aggression unconnected to the aggressive acts by certain landowners against those held as slaves, and as such the South had the moral right to stop it in any way possible.

Similarly one may examine the war against Iraq: was the goal to eliminate Saddam because he was tyrannizing his people, restricting their freedom, even torturing and killing them? No: it was to stop a potential and very vague threat, which brings to mind the old saw about a female interviewer criticizing a military camp teaching boys to shoot: "You're equipping them to become violent killers!" To which the blunt camp commander replies, "Well, you're equipped to be a prostitute but you're not one." We're all equipped to harm other people; freedom demands leaving people that potential until they demonstrate they are unworthy of it. Contrast when the US was attacked on December 7, 1941: we fought back in self-defense, not acting as initiators (I will leave for another place the debate over the need for using nuclear weapons on Japan except to say that response to aggression is not carte blanche; a subway shove does not justify murder in response).

Was the American Revolution justified? Was "taxation without representation" enough of a scourge to go to war? Given that other means had been tried, as spelled out at length in the Declaration of Independence, to all of which the king had turned a deaf ear, then certainly: rights were being violated and a rational man has a duty to himself to fight back. But "taxation without representation" did not go far enough. Is it any better to be coerced into action (perhaps into war, by a draft), or to have property confiscated, or rights restricted, if the majority in a particular surrounding geographic area has consented to it? No! So the objection ought to be instead to coercion of any sort, including taxation (which, if done by anyone but this theoretical body called government, would be mere robbery), and practically that was an objection one reads in the papers of the framers (chief among them Thomas Jefferson).

The Articles of Confederation did not allow for forced levies, and was primarily a consensual form of government with little interference. Even if such was not written into the document, the frame of mind of the rugged individuals of the time would not permit—at bayonet-point if necessary—interference into their individual and sovereign affairs. Even the Constitution did not allow most of the egregious thefts of today (e.g., the "New Deal" or "Great Society" social programs) and the same frame of mind of individual sovereignty reigned, so by twisting plain meaning and omission of things entirely obvious to the framers, the founding document has been found to support all these things by complicit executives, legislators, and courts. But in reality on the first day the first tax collector came to an American door and demanded of his increase, he had the thorough moral right to refuse, with whatever force (and companions) necessary if force was proffered, and we still have that right.

For one does not fight a revolution merely to pay the same taxes to a different overlord; one fights it to throw off a burden, to find that light yoke of an ideal government (or none at all) that acts with subsidiarity, that protects rights, that is unable to add aught to its power and remains weak enough that if it should ever do otherwise, it may be dissolved by withholding from it the private resources it needs to survive. So we find of the American Revolution: it was not fought to pass the same yoke from the hands of a distant tyrant king to the hands of a distant tyrant president, but because "We hold these truths to be self-evident, that all men are created equal, that they are endowed by their Creator with certain unalienable Rights, that among these are Life, Liberty and the pursuit of Happiness" and "That to secure these rights, Governments are instituted among Men, deriving their just powers from the consent of the governed,—That whenever any Form of Government becomes destructive of these ends, it is the Right of the People to alter or to abolish it, and to institute new Government, laying its foundation on such principles and organizing its powers in such form, as to them shall seem most likely to effect their Safety and Happiness."

A narrow construction of "consent of the governed" is warranted (as with the rest of the Constitution, intended to be a precise document if any document ever was); i.e., the consent of every one of the governed, and, lacking that, they can take themselves out of that group (as, at a larger level, states were able to leave the union up until the tyrant Lincoln's greed barred it), and form their own township or other body on their own land. The United States was formed with the noble goal of instituting governments whose sole role was to protect rights (leaving as much freedom as possible to individuals); with the novel goal of right trumping might: yet how soon we faltered!, and now someone who I acknowledge not at all as representative of me barters favors in a faraway capital with the result that they get to accumulate more power and my taxes increase and freedoms decrease. How would this be different if we were governed by the King of England? It is the sheep and the wolves voting on dinner; it is a group of thugs gathering around a victim and voting 10-1 to assault and rob him and feeling noble because they allowed him his one vote.

Our government has failed in its role of protecting rights, instead becoming the primary violator! May we not thus say with the colonists, of modern so-called government, "[They have] erected a multitude of New Offices, and sent hither swarms of Officers to harass our people and eat out their substance" and "[taken] away our Charters, abolishing our most valuable Laws and altering fundamentally the Forms of our Governments"? Should we not respond as they did, "That these united [People] are, and of Right ought to be Free and Independent [People], that they are Absolved from all Allegiance to the [present government],… that as Free and Independent [People], they have full Power to levy War, conclude Peace, contract Alliances, establish Commerce, and to do all other Acts and Things which Independent [People] may of right do.—And for the support of this Declaration, with a firm reliance on the protection of Divine Providence, we mutually pledge to each other our Lives, our Fortunes, and our sacred Honor."

Steak at 21 Central

News ·Wednesday December 16, 2009 @ 21:39 EST (link)

Honey and I just got back from having steak (she had the fillet, medium well; I had the New York strip, medium) at 21 Central in Kirkland. Nice little place, easy to find, street parking or park in the city lot behind ($1/hour between 5pm and 9pm). We dressed up for it, even though the place didn't require it: I worse a suit and tie, Honey wore a dress with a small jacket on top. It was Honey's birthday yesterday, and I also gave my final report for class yesterday, which went well—now we're both done school for the quarter—so this was a celebration of both (but mostly Honey's birthday).

Why I don't like "twitch" games

Media ·Wednesday December 16, 2009 @ 05:08 EST (link)

"Twitch" games don't require much thinking, just fast fingers. If you enjoy them, well and good—Honey enjoys Guitar Hero, and has fun with it (although it also frustrates her a lot)—but they're not my first choice. If i want to do something repetitive and routine quickly and accurately, I'll write a program for it and find something interesting to do while the computer does the busywork. In the past I've preferred to write programs to solve classes of problems, e.g., a Sudoku solver, a word jumble solver ("for" Honey, and used on Frank in Missouri), and a Minesweeper solver (while stuck at Buffalo airport overnight). A solved problem, especially one I can and have solved, isn't all that interesting to me; I'd rather write code to solve the whole class (or just develop a mental algorithm) than waste time on individual instances.

I suppose I prefer strategy games, which is why I liked Warcraft (III) for a while, but when it became clear that it had equal parts twitchery I lost some interest. Plus i confess I'm not the twitchiest gamer on the block and I'd rather build things and explore than race a machine that can always beat speed-wise anyway. Maybe I'll go off and play Zork now….

CSEP501: the compiler is done

News, School ·Tuesday December 15, 2009 @ 22:17 EST (link)

I had my final report for my CSEP 501: Compiler Construction course today; it was a 20-minute scheduled block with the professor; just a fairly informal discussion about how the project went. The project was to build a "MiniJava" compiler in Java targeting Intel x86 (32-bit). Variations were permitted with permission of the instructor (e.g., we used C++; others used F#, Python, etc., or targeted MIPS or Intel x86-64). For the first two parts (scanner and parser) I was in a group of two; we parted amicably after my partner realized I wanted do to several language extensions which (although I said I'd do them myself) and didn't think he'd have time that quarter; so I worked alone on type-checking, semantics, and the big final code generation project. My final project archive is available.

Now that I'm done, it's strange that my (GNU) Screen window #2 is no longer "501" and window #4 no longer "test"; I've had those windows set that way for months now, flipping back and forth as I worked on the source and ran tests.

Speaking of tests, one of the things that helped the most was having a lot of test programs that allowed gauging the state of the compiler at any given time. Toward the end, when code was generated, I had my test framework assemble, link, and run the tests that were intended to pass (I had another class that was intended to ensure the compiler detected errors when appropriate). The framework also compared the test output with known good output.

Another great help was using source control (Subversion in this case). Looking over the logs, I can find a few interesting points where good testing caught some bad problems which were all eventually fixed: Much of these were found by tests as said, and by having about 10 different debug options to allow dumping intermediate compiler states (the AST, IR before and after optimization, register assignment, add IR statements to generated code as comments, etc.).

As the project went on I tended to mark areas that needed fixing (where it was "good enough" now, or I'd used a temporary hack) with either "TODO" or "XXX" comments, which worked well: it kept the work items obvious and easy to find, and local to where they needed to be done. But in larger projects, they can become overused and get ignored: Word has many TODOs, most of which just don't matter any more (fixed another way; current algorithm is sufficient, etc.).

This is the final report I submitted, detailing the stages of my compiler.

CSE P 501 course MiniJava compiler project, part V - Report.

Tools (versions used in parentheses, although other versions may also work): C++ (GCC 4.4.1), GNU Flex (2.5.35), GNU Bison (2.4.1), SCons (1.2.0), Perl (5.8.8), Boost (1.39).

FEATURES

All features are believed to work, plus certain extensions (see below, EXTRA FEATURES).

TEST PROGRAMS

The test programs available from http://www.cambridge.org/resources/052182060X/#programs were used, as well as a few of my own, both programs designed to pass (test/*.java) and programs designed for the compiler to catch errors (test/error/*.{java,txt}). All programs in the main test folder compile, assemble, link (with the included mj library), and run to completion without errors (not all return 0; some with void main functions return nonzero, but none return error codes indicating premature termination). For the programs from the above site, I examined the source and ensured that the right results were printed; they were very helpful in diagnosing problems. Each program also has a '.out' file which is the verified output; the test/runtests script does a 'diff' against it and the actual output, which provides another level of security against bad changes.

PrintArgs.java illustrates the passing of command-line arguments and the handling of strings (an array of strings, in this case). PrintArray.java shows more array handling, including an array of base pointers to various derived classes.

IfNot.java illustrates an optimization to remove a 'not' instruction and reverse the jcc/setcc condition.

LongAdd.java and DeepArray.java were unsuccessful attempts to cause register spills.

VoidDivide.java illustrates optimizing out (most of) a divide in void context (we don't care about the numberator, just if it divides by zero).

Or.java tests the boolean or (||) extension, using System.assert(), which would cause test/runtests, the test host, to fail if any asserts fail.

SpillTest.java has a deeply nested hierarchical comparison, which ensures we run out of registers, and exercises the spill code.

EXTRA FEATURES

Most extra features were completed for the parser assignment, thus they are described in README.2. Optimizations are described below in the appropriate stage under DESCRIPTION.

DESCRIPTION

The compiler runs several stages and passes and each does particular transformations on the input tree or list, or produces a new representation.

0. Driver: The process is driven via the argument parser in main.cc and the driver class (SPD, driver.h) which runs the pipeline (SPD::Parse) and provides context (e.g., command-line options) and global functionality (e.g., error reporting). To avoid unnecessary error checking, if one stage fails the pipeline is usually aborted (e.g., after type checking the code would bloat enormously if later stages had to account for undefined types).

1. Scanner: (see scanner.l and README.1; extensions include "void", other comparison operators besides "<", divide ("/"); also "this", "super", and "System.out.println" are not keywords; they're general identifiers handled later). Scanned tokens have location information embedded.

2. Parser: (see parser.y and README.2 for language extensions). The parser creates an AST of nodes inheriting from the base syntax node (SN, node.h), the main types being expressions (XN, exp.h), statements (CN, stmt.h), and declarations (DN, decl.h, which also includes classes, SNC/class.h, and methods, SNM/method.h, and the top-level program, SPD/driver.h). Nodes contain a generic list of children; most have specific accessors to improve readability (e.g., binary expressions, XN2, have XnLhs and XnRhs child accessors). If the number of children is indeterminate (e.g., parameters), a secondary container node is used.

3. System: SPD::SPD creates the static methods System.out.println, and a few handy extensions: System.out.print (takes a string parameter), System.abort (calls C library abort()), and System.assert (calls abort if passed boolean is false). The String built-in class is also created here. System classes may not be inherited from, and only String may be instantiated. The implementation is provided in the target mj library (see mjlib.cc).

4. Debug: along the way there are several possible debug print-outs, controlled by flags (see main.cc, or mj --help). --debug-scanner, --debug-parser, --debug-gen, --debug-reg print debug output during scanning, parsing, code generation, and register allocation respectively. --print-ast, --print-sym, --print-ir-pre, --print-ir-post, and --print-live output the AST, symbol tables, IR (before and after optimizations), and live ranges. --debug-code inserts some debug comments into the generated code.

5. Fixups: (fixup.h) Since classes can be used before declaration, this pass links type information to named classes (whether base classes, declarations, etc.). This is aided by a declaration reference type (DR, ref.h) which uses a boost::variant to store either a class name or a pointer to a declaration (DN).

6. Type-checking: (typecheck.h; see README.3) Each expression node (XN) is assigned a type, which it gets from its content (constants) or children (operators). The TI class (type.h) stores type information and has an FSubtype method to check if one type is a subtype of another. TCV::PtiTypeCheck ensures that argument types match when they need to, even when an operator can take different types (e.g., my ==/!= can also compare boolean values or class values). Method calls take on the type of their return value, and arguments are checked against declared parameters. The destination of an assignment must be a subtype of the source (e.g., Base b = new Derived() is allowed). If a method name matches a base, its parameters and return type must match too. And a non-void method must end with return (required check due to my extension making return a general statement).

7. Contexts: (context.h) Borrowing a page from perl, three contexts are defined: void, boolean, and value. Void context occurs when the result of an expression is not used; boolean context is an optimization to allow certain comparisons to pass their results in flags. Expressions in void context can be removed from the AST entirely except for method calls and division (since it could be a division by zero which has the side effect of terminating).

8. Measuring: (quant.h) Determines sizes for classes, vtable offets for non- static methods, and frame offsets for parameters and local variables. If local variables aren't used, they don't take up any space (very basic check).

9. IR: (ir.h, irv.h) The IR visitor builds a linear, 2-operand IR. (In retrospect, a 2-operand IR is simpler which is both good - it's a lower-level representation in which the universe of instructions is more restricted - and bad: some complex expressions require multiple IR instructions.) IR operations are basic (set, store, load, arithmetic, call, jump, label) and the allowed operands are constants, temporaries (future registers), labels, the frame or stack pointers, "this", and a conceptual return value. We also build a string table in this step; duplicate strings are coalesced.

10. Constants: (const.h) (This series of IR manipulators, inheriting from class IM in ir.h, is evoked from CGV::GenerateCode in code.h) This IR manipulator replaces temporaries set to constant values with the constants themselves, and also replaces series of constant expressions with the evaluated result. It also eliminates identity operations (add/subtract 0, multiply/divide by 1), and either removes or removes the condition from conditional jumps based on a constant.

11. Jumps: (jump.h) A few IR manipulators here snap jumps to jumps, remove jumps to immediately following code, and remove dead code (code between an unconditional jump and the next label, after removal of unused labels).

12. Frame: (frame.h) This IR visitor checks if the frame pointer is used. If it never is, we may be able to optimize it out later.

13. Instruction selection: (insn.h, low.h) This final IR visitor generates machine instructions (a list of LL objects). It is primarily a direct translation of the IR, with some optimizations (e.g., t0 <- FP, t0 += const, t0 <- (t0) can be matched to a single instruction). A few marker instructions are emitted to help with register allocation: start of call, end of call, epilog, prolog.

IR temporaries are still temporaries, but some register names are emtited (see e.g., LloFromOpr in insn.cc): "this" becomes ECX, return value is EAX, frame/stack EBP/ESP. Some registers are already marked as being required, defined, or used by certain instructions (see LL::DefUse in low.cc). Some register affinities are set: e.g., "idivl" uses EDX:EAX and outputs to EAX, "cdq" requires EAX and outputs EDX:EAX, and "set<cc>" requires (the low 8-bits of) EAX, EBX, ECX, or EDX on the x86 (restrictions loosen with x86_64).

14. Peephole optimizer: (peep.h) Doesn't do very much, although I had hoped to do more by storing symbolic values of the expressions in live registers and eliminating temporaries that reuse these values.

15. Register assignment: (reg.h) Manipulates the low-level instruction list by "painting" temporaries with register names. It first walks the instruction list and finds live ranges, by tracking when a temporary or register is first assigned to, when it's read, and when it's reassigned (it is an error to use an undefined temporary or register; we don't generate such code; this is not related to undefined variables, which are at a higher level, although similar code could be used to detect them earlier). ECX is artificially added as live for the whole method for non-statics.

Next, an interference graph is built, and registers are assigned in order (a cleverer algorithm could be used, but I never found a case where it was necessary, although this is not to say they don't exist; I posted to the discussion board to ask for input here). All live registers are saved/restored around function calls. This is not optimal, since the platform only requires EBX, ESI, and EDI to be saved, but I decided the internal conventions would be that only EBP need be saved, since at this point saving registers in the prolog would be difficult (it would either require modifying EBP offsets or later compound statements); this is another case where a 3-operand IR could have passed along more information and made it easier to adjust after the fact.

If no registers are available, a temporary's adjacent registers are examined; we pick the least-used candidate that doesn't collide with us, and save it around our definition/use ranges. (Collision means that the register's definition and use is interleaved with the temporary.)

E.g., in this hypothetical code segment, t3 denoting an unassigned temporary: 
... (%ebx populated earlier)
    1 movl $5, %edx
    2 movl $10, t3
    3 addl %ebx, t3
    4 movl -4(%ebp), t3
... (%edx used later; %ebx and t3 not used again)
%edx is live in [1, >4], %ebx is live in [<1, 3], and t3 is live in [2, 4], so %edx is a good candidate for t3 (since its definition is before t3's and its use is after, i.e. it encloses t3 completely) but %ebx is not, since its use is interleaved with t3's.

16. Peephole optimizer: (peep.h) Run the optimizer again to see if it can do anything after register assignment or other modifications.

17. Clean: (CLN, low.h) remove any marker instructions (they're emitted as comments if they do get to the listing, so for tidiness only) unless --debug-code was specified.

18. Output: generated code is written either to stdout, or to a file specified by the --output (-o) parameter. We don't do any assembling or linking, although the Python program test/build will, as will test/runtests, assuming the GNU toolchain (as to assemble, and g++ to link, since libmj is built as C++).

There is a list of optimizations I considered (but lacked time for or the design didn't match well with them) in the file src/OPTIMIZE.

To build and run the test programs, cd to test and run ./runtests. It will just show success/failure, but it leaves the output so assembly/binaries can be examined/run afterward. I have included the assembly in the archive.

XBMC: hide reboot and shutdown options

News, Technical ·Tuesday December 15, 2009 @ 05:57 EST (link)

Since I run XBMC from MythTV, I just want a way to return to MythTV; I don't need the extra reboot/shutdown/hibernate/etc. options on the home menu. Fortunately this is easy to change. Find the directory defining your theme (skin); in my case, /usr/share/xbmc/skin/PM3.HD, for Project Mayhem III (HD), and find the file Home.xml (most likely in a subdirectory such as 720p). Edit it and find <onclick>ActivateWindow(ShutdownMenu)</onclick>; change it to read <onclick>XBMC.Quit()</onclick>, and save. If you just want to modify the shutdown menu, rather than having clicking the red power button exit XBMC, edit DialogButtonMenu.xml. If you also want to get rid of the Favorites menu, find <description>Favourites push button</description> and add <visible>false</visible> just below it. (Thanks to cptspiff in Freenode #xbmc for help with this.)

DVDs finished: Star Trek: Deep Space Nine - Season 7, The Karate Kid, The Karate Kid Part II.

Vacation until the end of the year

News, Work, Photography, Guns ·Sunday December 13, 2009 @ 07:18 EST (link)

I'm on vacation until the end of the year (actually January 2nd, since New Year's Day is a Microsoft holiday). It wasn't exactly by choice; we can only keep twice our annual vacation time; anything over that is subject to forfeiture. I calculated what I'd lose and worked backward from the end of the month, skipping company holidays, and ended up with the 11th.

So far I've been spending most of my vacation on the "MiniJava" compiler for my Master's class, so haven't had much time to relax.

Given the length of vacation (and the price of plane tickets and discomfort of flying in general), we'd considered driving across the country to both our parents' for Christmas, but my camera died, and I sure wasn't going to drive all the way across the nation without a way to take pictures.

The camera, my Nikon D300 was found dead on Thanksgiving, when I brought it in from my car: it alternated between the display not showing anything, to showing the normal shots remaining count that appears when it's off, but not turning on. I don't know what caused the problem; possibly condensation from being in the car (it was just in a soft case). Glazer's, where the camera was bought in December 2007 (not by me; I got it used a few months later when the seller upgraded to a D700), recommended I either send it back to Nikon (long wait) or try nearby repair shop Photo-tronics. Their estimate was just under $500; I decided to go ahead with the repair. (Note: parked at nearby "green" shop parking lot, since said lot was nearly empty.) When I go back to pick it up I may try to sell Glazer's my D100 or F90X, and maybe my Tamron 28-200 lens.

We got a membership (silver annual "family") at West Coast Armory's new indoor range in Bellevue (brochure with rates). It's disappointing that they don't allow steel-cased ammo; many indoor ranges don't because it interferes with the machines that their shell casing pickup company uses. So I either need to re-up my SVRC membership, go to the Sultan pit a lot, or try to sell my steel-cased 7.62x54R and .223. In any case I need to try to find brass-cased in both calibers (I suspect 7.62x54R will be less common, since most surplus is steel-cased).

Books finished: Unfair Competition: The Profits of Nonprofits.

Discovering XBMC; connecting it to MythTV

News, Technical, Media ·Friday December 4, 2009 @ 19:10 EST (link)

Even with the 0.22 release I'm unhappy with MythTV's UI, especially for videos. Although, for example, most of my movies are found so their thumbnails show up in the selection screen, the images are tiny unless you go to the trouble of selecting one. Its TV episode lookup apparently won't find my episodes (since they're not named according to its rigid conventions). And even with the new 0.22 themes it's not as slick as one would hope with all the graphical abilities available. And it's not that configurable. For example, recently I thought I'd like to allow the user to select which movie poster image is used (rather than using the first one available on TMDB). So I went browsing for something else, and came across XBMC (originally XBox Media Center, now adapted to other systems including Linux, and renamed to the somewhat redundant "XBMC Media Center"). The graphics are very slick and it's extremely configurable, with an embedded Python (2.6) interpreter (looks like it would be easy to upgrade to 3.1 if I wanted to) that can be used for scripts or "plugins", which are sort of like virtual file systems (e.g., there is one that makes MythTV's recorded programs appear as a folder), with some useful built-in functions, including ones for windowing and dialogs.

I found a way to add a button to MythTV's "Media Library" menu to launch XBMC, but it was a little harder to determine how to give that button an icon (turns out you set the <type> to something unique, like XBMC and specify an icon for it in the theme's menu-ui.xml file; or rather, two, at least for the default Terra skin: one for when it's active (visible), and one for when it's selected. I couldn't find any images of the right size, so I grabbed one from the XBMC site, scaled it to match the other icons, and made an "active" version in Photoshop with a transparent lightning overlay, as seen here.

You are welcome to use them if you need XBMC buttons for MythTV. We'll probably still use MythTV for recording TV programs, so we need a way to go back and forth.

(Paths are for Gentoo; modify to suit.) To add the button, copy /usr/share/mythtv/themes/defaultmenu/library.xml to the .mythtv directory of the home directory of the user that MythTV runs as (usually /home/mythtv), and add the following right above the closing </mythmenu> tag: 
    <button>
        <type>XBMC</type>
        <text>XBMC</text>
        <description>Launch XBMC</description>
        <action>EXEC /usr/bin/xbmc -q</action>
    </button>
(Alternatively, grab this file, but there's a risk of missing intervening updates.) As written, this will give you a button with the unsightly white on black text "No image available" (note that you'll need to leave and re-enter the menu to see the new button, but you don't need to restart MythTV). To give it an image, save the two images here as (left) xbmc_off.png and (right) xbmc_on.png in /usr/share/mythtv/themes/Terra/watermarks. To have them show up, add the following to both the end of the <state name="active"> / <statetype name="icons> and the <state name="selected" from="active"> / <statetype name="icons> blocks (i.e. after the <state name="ZM_EVENT_VIEWER" from="ZOOMFINDER"> block): 
    <state name="XBMC" from="default">
        <imagetype name="icon">
            <filename>watermarks/xbmc_on.png</filename>
        </imagetype>
    </state>
Alternately (again risking missing an intervening update) you can use this file. Note that you unfortunately can't use a local version of this file as was possible with library.xml. You need to restart MythTV (exit it and depending on your setup, it should auto-restart, if not, relaunch it by restarting X, usually with startx; if you've disabled exiting, you may need to kill X with ctrl-alt-backspace; if that's disabled (as newer X.org servers do), you may need to kill X remotely. The image should now show up in Media Library, with the lightning bolt overlay when selected; clicking it will launch XBMC. Default ("confluence" skinned) XBMC can be exited by moving left to the "Power" button and selecting the red "X" (my remote "just worked" for moving and selecting; YMMV).

Next step: add MythTV as a video (and perhaps music) source. That will be fine for now, but eventually I'll want to have XBMC track videos only, so I can used its improved scripting and plugins without going through MythTV. I hope this was helpful—I didn't find anywhere else online with all the steps. No doubt I'll have more to say about XBMC as I use it: hopefully all good.

Books finished: Ayn Rand Answers, The Cat Who Walks Through Walls.

MythVideo upgrade: better metadata

News, Technical, Media ·Friday November 27, 2009 @ 23:30 EST (link)

I recently upgraded the MythTV box (to the current Gentoo ebuilds, including 0.22 the MythTV application). I did this to get some new features of MythVideo including improved metadata storage and lookup for videos and TV shows. The new themes look nice too, for the most part; sometimes text is too small, and since I don't have cover art/posters for most of my movies/shows there are a lot of very big images of question marks (or blanks). But that will be remedied. The included scripts in /usr/share/mythtv/mythvideo/scripts (mainly tmdb.pl and ttvdb.py) that find episodes (using TheTVDB.com and themoviedb.org) are a reasonably good place to start, but they don't conform too well to my naming conventions. Fortunately they are both in languages I know extremely well: open source means you can make things better, and fairly easily (even if it's just a local benefit); it's a knowledge economy.

Having posters for most movies makes the MythVideo browsing UI pretty nice. By default, the shortcut key W will by default invoke one of the two scripts above (configurable, of course; so I could fix the scripts or replace them with my own) which will pull metadata from one of those two free sites (there are other scripts that will use IMDb or other sites as sources). They have a well-defined interface as to how information is communicated between them and MythTV.

For instance, it would be nice to be able to select the poster used for a movie visually. Is it possible to pop up a UI from a script within an existing X session? I don't see any reason why not; and indeed, the PyGTK tutorial's hello world script works great. (I went with GTK because Tk and Motif and wx and the older ones looks butt-ugly and have severely limited functionality.) It can even be done from an ssh session as long as it's prefaced by export DISPLAY=:0.0 (as appropriate). (It's lousy that it segfaults if DISPLAY isn't set, though.)

So what's wrong with the tmdb.pl and ttvdb.py scripts? Why not use them and be happy? Perhaps I can, but these are the hurdles:

  1. They don't understand my naming convention. For example, I group some movies into directories and remove redundancies, e.g. Harry Potter/1 The Philosopher's Stone (the 1 keeps the order correct; there isn't a sort override field in the videometadata database). The script tries to find a movie called "1 The Philosopher's Stone" rather than keeping the directory and stripping the numeric prefix. If I used the full names (Harry Potter and …) they'd still be out of order (alpha-sorted). Possibly fixable by modifying the script itself, but then I'm doomed when I upgrade.

  2. It picks the first movie poster available; I'd like to be able to select one (see above regarding PyGTK). E.g., the first poster for Transformers: Revenge of the Fallen is pretty dark and gloomy and uninformative.

  3. When the database is rescanned, old metadata is destroyed and has to be re-fetched from scratch, meaning unnecessary and slow network traffic, and items with multiple matches have to be user-selected again. Granted, one fix is to just not run "Scan for changes", although I don't know what MythTV will do to the database in future. But this can be overcome by automated database backups.

  4. I want to tie it in with my DVD watch list.

There's a useful new utility called Jamu (Just Another Metadata Updater—really, those names aren't clever any more, people, although at least it provides a recognizable and unique program name). It can do lookups for various metadata and artwork, so I'll certainly make use of it in my own utilities.

Aside from the MythTV stuff there was the usual collection of blocking package issues which eventually got sorted. The Myth box needed 430 packages; then I decided to emerge -uDNv world on the server too, which also had its share of issues. For a while I had some corruption on torrents created by one machine on a (Samba) shared directory on another. When I upgraded both to kernel 2.6.31 the problem went away; I'd narrowed it down to Samba (vs. LVM or something else) being the culprit, and there were fixes for CIFS corruption between my old (2.6.28) kernel and this one.

Speaking of database backups above, I borrowed a script from another machine and started automatic backups of the MythTV database. I suppose I can just use the videometadata table if I can be confident that it won't randomly disappear, or if it does, I can get it back with minimal hassle. (I never need to actually rescan for new content, since I already have programs that monitor my video directory with inotify and add videometadata entries appropriately, and a non-destructive scanner.

Given the current cost of HD space (e.g. an external USB 1.5T drive is a little over $100 today at Newegg.com), it's almost as cheap to record data (show episodes, or whole DVDs) on a (potential chain of) USB HDs (possibly linked as a logical volume, or symlinked from a common directory) than it would be to use DVD±Rs or (given the stage of development—8x and 12x burners are rare and expensive, especially external—and burn speed, and low penetration compared to DVDs) Blu-Ray disks. Perhaps Bob is onto something, at the current price point.

I also installed MythMusic, but need a tiny utility to set ID3 properly (just something simple that uses the directory and filename) (Mutagen, a promising Python ID3 library). When the TV suspends or powers down it also turns off the music (since it goes through the TV to the amp), so I increased the blanking time in xorg.conf.

Useful modules: IMDb lookup in Perl (IMDB::Film; tested, works) and Python (imdbpy); Python 3 (what I'm using but modules can be hard to find since it's relatively new) PostgreSQL module.

<Previous 10 entries>