Monday, 31th May, 2010
iMac G3
Sometime ago, I was lucky enough to acquire a 1998 or 1999 era iMac G3, Bondi Blue, 96MB of RAM (6MB shared with the video card, I think), 8GB hard drive, 333MHz G3. Many thanks to the Computer Recycling Project at The University of York.
And for sometime, it sat on my desk, mocking me. I couldn’t get it to work. It just sat there, looking pretty and smug with itself. I tried to do a netinst of Debian 5.0 on it once before, but it failed somewhere along the lines.
Fast forward to a few weeks ago, and I move house, and I get it all set up in my new room — The LAN port is near at hand, my laptop gets WiFi, so I don’t have to share the connection. I can get going with the machine that I’ve since christened “Lovelace” after Ada Lovelace.
Clearly, the University network hates this machine, it doesn’t have wpasupplicant on the netinst CD, I can’t connect. I am forced to install a very basic system on to it. Which I do. I then spend an evening getting the wpasupplicant deb files, and a few other packages and installing them. With this done, I eventually get a working network connection!
Then comes the big task, getting a graphical web browser up and running. I decided to go with FluxBox and IceWeasel (Basically a re-branded FireFox). All is good!
Eventually, after fighting with the xorg.conf file for a while I get it work. Of course, the first thing to do is some Eulering.
As it turns out, it run GHC (The Haskell compiler I usually use) really quite well, if a little slowly. Also, all of the algorithms I’ve written run at least 10 times faster on contemporary machines, leading me to infringe upon the 1 minute rule for some problems. Ooops.
I’ve yet to try Python on here, but it’s only Python 2.5, where I’m looking to move to Python 3.x asap.
TL;DR I got an epic new machine that I wish I’d had longer that runs so slow, but it’s so cute.
Note: It can also play CDs! Joy!
Friday, 14th May, 2010
x86_64 Assembler, Part 2
So, once again I set forth into the wilderness of asm programming, with very little to help me, bar a 64-bit Intel Core 2 Duo (I think… it was a uni box), a few friends busying themselves with work beside me, and the help of those on IRC. It was going to be a long night.
Having already overcome the main hurdles of working out how to print an answer to the screen, how to get it to assemble and link, and the basics of GCC, I just had to get two loops working nicely together. No biggy. Problem 6, possibly one of the easiest out of the first 10.
The first part was simply about getting the sum 1^2 + 2^2 + … + 100^2.
sum_squares: ; Begin the calculation, rax = 1^2 + 2^2 + ... rbx^2 ; First, save the registers to the stack. push rbx push rcx push rdx push rsi ; Next, set the initial values mov rcx, 0 mov rsi, 1 mov rsi, rax loop_sum_squares: mul rax ; rax = rax^2 add rcx, rax ; Add it to the accumulator inc rsi ; Increment the loop counter mov rax, rsi ; Prepare for the next iteration cmp rsi, rbx ; See if we have to do the next iteration je sum_sq_ret ; We reached the limit - go to the exit sequence. jl loop_sum_squares ; Not reached it yet, keep looping. sum_sq_ret: ; Exit sequence. mov rax,rcx ; Put the result in rcx. ; Restore the registers to their original state before leaving. pop rsi pop rdx pop rcx pop rbx ret
The sum_squares is simply a driver function, ensuring that the accumulator is 0, saving the registers and so forth. loop_sum_squares is where it all happens, rsi is the loop counter, keeping track of where we are, and rax is where the squaring is done. Once it’s squared, it’s added to the accumulator in rcx. It then checks rsi and rbx to see if we’ve reached our limit. If we have, jump to the exit procedure. If not, continue looping.
The code for (1 + 2 + … + 100)^2 is vastly similar, relying on a counter and an accumulator.
sum_to: ; Save the registers push rcx push rdx ; Initial accumulator value mov rcx, 0 loop_sum_to: add rcx, rax ; acc = acc + current inc rax ; current++ cmp rax, rbx jl loop_sum_to ; if rax < rbx, continue looping je sum_to_ret ; else go to the return sequence sum_to_ret: mov rax, rcx ; put the result in the right place ; restore the registers pop rcx pop rdx mul rax ; Square the sum. ret ; return
Now all that I needed was to call these and find the difference between them. Not hard at all.
section .text global _start section .data msg db '%lld', 10, 0 extern printf extern _exit _start: mov rax, 1 ; 1^2 + 2^2 + ... +101^2 mov rbx, 101 ; limit call sum_squares push rax ; save the result for later mov rax, 1; call sum_to ; rax = (1 + 2 + 3 + ... + 100)^2 pop rbx ; rbx = 1^2 + 2^2 + ... + 100^2 sub rax, rbx jmp write_result write_result: ; write the result to the screen mov rsi, rax mov rdi, msg mov rax, 0 call printf jmp exit exit: ; Call the exit system call. push 42 call _exit
Simple, really. Mathematically simpler than problem 5, actually. And a brief comparison between this implementation and the Python one:
dst502@milan:~/Code/asm$ time ./euler6 XXXXXXXX real 0m0.002s user 0m0.000s sys 0m0.002s dst502@milan:~/Code/asm$ time python ./euler6.py XXXXXXXX real 0m0.064s user 0m0.047s sys 0m0.004s
Clearly, the asm is faster. But bear in mind, it took me around 3 days to write the asm versions of problem 5 and problem 6, whereas the Python versions took barely 10 minutes between them.
Done! :-D
Saturday, 8th May, 2010
x86_64 Assembler, Part 1
Oh god. Oh god. WHY IS rcx BEING SET TO 0?!
This was effectively an exercise in getting to grips with x86_64 and gdb. Both powerful, both requiring years of use to really “know”.
Either way, I had a dabble, tackling both problem 5 and problem 6 in assembler. This blog post will cover problem 5.
A real challenge was that I’d never had used an assembler, or a linker, so I had to get those working along side getting my code to work. I chose to use the Linux system calls for getting output from my program, since I don’t actually know how those work deep down, but they’re there.
For my assembler, I settled for nasm, and for linking, I left that to GCC. I used nasm because it was what I first came across (with regards to tutorials) and it seemed to be the most likely to “just work” without additional complexity.
So in total, I had to work out:
- x86_64 Assembler
- nasm
- GCC linking stuff
- GDB
- Use of Linux system calls at a low level
To get both problem 5 and 6 working correctly took well over 3 days of on/off hacking.
I first set about writing a Greatest Common Divisor algorithm, using subtraction as opposed to division, because I’ve always been told that division is slow. Also, it seemed easier to implement a subtraction based algorithm in asm than a division one.
gcd: ; calculate the GCD of RAX and RBX. Leave the result in RAX push rbx gcd_st: ; Start of the GCD loop cmp rax, rbx je gcd_ret ; If a = b, return (a) jl gcd_lt ; elif a < b, return gcd(a-b, b), jg gcd_gt ; elif a > b, return gcd(b-a, a). gcd_ret: pop rbx ; Put rbx back where it was :-p ret gcd_lt: sub rbx, rax ; b = b - a jmp gcd_st gcd_gt: sub rax, rbx ; a = a - b jmp gcd_st
Oddly enough, to actually get that written down on paper was surprisingly easy! After that, I just needed to use it for a Lowest Common Divisor function:
lcm: ; Calculate the lcm of rax and rbx, leaving the result in rax. push rbx push rcx push rdx push rax mul rbx ; a = a * b mov rcx, rax ; c = a * b pop rax ; a = a call gcd ; a = gcd ( a, b ) xchg rax, rcx ; swap a*b and gcd(a, b) div rcx ; a = ( a * b ) / gcd ( a, b ) pop rdx pop rcx pop rbx ret
Quite simple really… note the pushes an pop’s at the beginning and end respectively. I wanted to save the state of the registers before entering the procedure. After that, it is a simple implementation of (a*b) / gcd(a,b).
That’s the bulk of the program right there, the rest of it is simply looping trough the numbers 1 … 20 and finding their gcd with an accumulator.
; Entry point section .text global _start ; The printf format string, "%lld\n". section .data msg db '%lld', 10, 0 ; Get access to the two system calls we need. extern printf extern _exit _start: mov rax, 1 mov rbx, 2 call loop_start loop_start: ; Begin the calculation, note that rax is an accumulator. call lcm ; rax = lcm ( rax, rbx ) inc rbx ; rbx++ cmp rbx, 21 ; if rbx >= 21... je write_result ; then exit jmp loop_start ; else continue looping write_result: ; write the result to the screen mov rsi, rax mov rdi, msg mov rax, 0 call printf jmp exit exit: ; Call the exit system call. push 42 call _exit
Ow! That took me the better part of a day and a half. Calling printf especially. Most of the tutorials out there are aimed at x86, not x86_64. This causes quite a lot of confusion. Especially when you use GCC & C to write some assembler that uses printf and it just uses 32-bit methods.
And for good measure, I put the lines to assemble and link it in a shell script:
nasm -f elf64 euler5.s gcc -nostartfiles -o euler5 euler5.o -lc
And of course, let’s see how long it takes to run (With the python version I wrote much earlier for comparison):
dst502@milan:~/Code/asm$ time ./euler5 XXXXXXXXX real 0m0.022s user 0m0.020s sys 0m0.002s dst502@milan:~/Code/asm$ time python euler5.py XXXXXXXXX real 0m0.047s user 0m0.039s sys 0m0.007s
A massive thanks to those on ##proggit who helped me suss out nasm, gcc and x86_64 in general, GeDaMo, ryan[WIN], I’m looking at you :-p
Done! :-D
Tuesday, 4th May, 2010
Politics
I know that this is a programming blog. And I know that I don’t, haven’t and most likely, will never get the chance to study politics. Either way, here is my £0.02 on the current (2010) General Election, especially with regards to the BNP, why I will be voting, and how I came to the conclusion to vote for the Liberal Democrats.
Stylistic
The British National Party
The BNP’s is very efficiently laid out. Almost everything is neatly categorised, and every point begins “The BNP…” as if one needs reminding about which manifesto is being read. Not that it’s easy to mistake the policies of any other political party (Cough, Nationalsozialistische Deutsche Arbeiterpartei, circa 1920 - 1930).
Every policy is summed up in a single bullet point, no expansion as to what it could mean for the British people, almost as if it doesn’t matter. Simply, “We’re going to do this, to hell with the consequences”. This manifesto is aimed at those with the lowest attention span and lowest reading levels, conveying the minimal information as simply as possible is the goal here.
Only once you dig further into the manifesto do you get some thing more: Paragraphs! What a novel concept. In these sections they do explain themselves, sort of.
The Liberal Democrats
The Liberal Democrat (LibDem) manifesto proceeds at a much more leisurely pace. In the Pocket Guide to their manifesto, each point is laid out with a paragraph. There’s a brief sentence in bold for those who wish to scan text for key points. After that, each point is well expanded on. What they will do, why they are going to do it, and what it will mean (very briefly) for any citizen. The full manifesto is oddly, the reverse, once again falling back to bullet pointed lists.
Unlike the BNP’s simplistic sentences, there’s usually a few sentences in each bullet point.
The manifestos are stylistically aimed at different audiences, the BNP’s makes the assumption that the reader is stupid, and lack’s basic English reading skills. The LibDem’s makes the assumption that you can get higher than a C at GCSE English Language.
Policies (repugnant and wonderful
The British National Party
“The BNP will institute a Community Award Scheme for young people”
That’s all the manifesto says about this. There’s no explanation of what it is, no explanation of what it will entail (cost-wise), and no explanation as to why.
What it actually is is a scheme where school leavers will entered into a compulsory community service scheme. That’s right folks, treatment usually reserved for criminals is going to be given to all 16 - 20 year olds! Oh joy! I can feel the BNP Youth Movement coming on right now, along with “Great is Griffin!” along with salutes.
As for the cost, it’s not mentioned, neither is how the young people will be trained for working in the community. A dearth of information is all that’s needed to cover up a bad and vague policy.
“The BNP will forbid the development and importation of genetically modified produce.”
So, GM is bad? Ah I guess we’ll have to throw away all of our bananas, domesticated dogs and cats, pigs, cows and anything else that humans have artificially selected over the last few thousand years f agriculture.
The only difference between artificial selection and genetically modifying the crops/animals directly is that instead of hoping that what we want will randomly happen, we make it happen. Increased yield to help feed our growing population at a lower cost and any excess can be sold to other countries for profit, or sent as aid, depending on your actual policy.
In short, the BNP wants to starve you and future generations. Nice!
“The BNP will repeal the Race Relations Act and all other far leftist social engineering projects, such as the Equalities and Human Rights Commission aimed at enforcing multiculturalism.”
Repeal the Equalities and Human Rights Commission?? Well, I suppose that treating other people fairly and such is simply a quality that’s not very British/Aryan. This one policy speaks volumes about the party.
“The BNP will deport all foreigners convicted of crimes in Britain, regardless of their immigration status.”
I don’t care that you’re a paediatrics doctor working at Great Ormond Street Hospital. You got a speeding ticket while going to work. That’s a crime, get out.
Another short sighted and ultimately racist policy. There will be lots of people who are affected by this. As far as I’m aware, I’m a foreigner in their policy, despite both my parents being born in the UK. So if I get a speeding ticket, I’ll be deported.
Thoughts
At a glance, their policies are very close to that of the Nazi party. Socialising of nationalising massive chunks of the country, for example, anything which falls under the banner of “telecoms”.
Also, in the sections in which things are explained in full, it becomes very clear what the BNP are all about, they’re not for the British (given their definition of British) people, they’re simply against everyone else. All of their policies stem from “mass immigration”. I’ll concede that we do not have enough housing to support the numbers of people that we’re getting, what we need is control, not an absolute ban.
An interesting quote from their section on the relation of race and crime:
“According to official figures, over 77 percent of adult black males between the ages
of 18 and 35 are on the police’s DNA database.”
First and foremost, the DNA Database does not care if you were convicted or not. If you’ve been arrested and had a sample taken you’re on it. This is compounded by the fact that the police force has the tendency to be biased with who is arrested. Being black makes you more likely to be arrested because you’re black; there’s a sizeable portion of the police force that is racist.
Quoting the DNA database as a way of legitimising one’s claims only legitimises the problems that the police force has with racism.
The Liberal Democrats
“No more landfill, a lot more recycling and a lot less waste”
Landfill can be good, if we only put biodegradable material in it, as was common 50 - 60 years ago. Landfilling cars and such is clearly a bad idea. Who wants to dig up an old dishwasher?
Moving everything to recycling can be difficult and expensive, recycling most of a car is easy enough, but what about a laptop, or an LCD TV? They often involve very energy-hungry processes, which we’re currently supplying with fossil fuels.
a good idea, in principle, but the devil’s in the details.
“No to nuclear and dirty coal”
No to nuclear is what I have a problem with here. Nuclear power is the only clean way to produce large amounts of power. If we were to build nuclear power plants to replace their fossil fuel counterparts, we could keep going until we had a much better renewable system in place. Solar and wind are unreliable at the moment, and we need to buy ourselves time in the form of nuclear power plants.
“Give people a say in policing and the NHS”
We will create directly elected health boards and police authorities so these services deliver what you need.
A say in policing and the NHS… This means voting in police chiefs and doctors. Hopefully they’ll only get to stand for election to these posts will have shown that they are fully qualified. Wouldn’t want homoeopathic doctors, or racist police chiefs now, would you?
If they implement this, they’ll need incredibly stringent controls on who gets to stand/.
“Give you the right to sack MPs who have broken the rules”
Two words: Shit yea.
“Cut red tape for putting on live music”
I fully agree with this, I love live music, and I want to see it in as many places as possible. Especially acoustic music. =^.^=
“Introduce a Freedom Bill to restore and protect our civil liberties”
Just look at this:
Liberal Democrats have put together all the freedoms that have been undermined by Labour and the Tories in the last twenty years to restore them in a single Act of Parliament. We will scrap ID cards; get innocent people off the DNA database; regulate CCTV; allow people to protest at Parliament; stop councils from spying on people; and stop unfair extradition to the US. See http://freedom.libdems.org.uk/
Thoughts
Despite their some of their policies seeming slightly under informed, they’re generally in the right direction for me.
There’s not a hint of racism, and they even cater for the LGBT community. I can see why some of their policies may not sit well with people, their policies on nuclear power plants and such, but otherwise, they’re the best party going.
Closing Remarks
The Liberal Democrats are all about freedom and well being for our country. The British National Party are all about limiting the possible well being of our country by destroying our current culture.
If you feel I’ve made a factual error, then please let me know, using the comment system.
Saturday, 13th March, 2010
Musically Inclined
So this particular week has been an odd one. Hence a diversion into a mad world.
On the one hand, I’m getting nitty-gritty in my course, writing a lexical analyser in C, bashing my head against Haskell, and Mathsing it up in general during the day.
But by night… Music! Lots of music! Firstly, I picked up a new guitar from The Guitar Shop in Beverley. I bloody love it, Vintage V300-MH. Sounds gorgeous, and the price ain’t to be sniffed at.
I showed my face for the first time at Band Soc here at uni. Had a great time jamming with a couple other folks, listening to some pretty cool improvised stuff.
Then I went to two gigs: Grammatics at StereoYork. I’ve already seen Grammatics once, so I knew I was in for a good night. I’ve liked their music from the first chord I heard them play. But their new material is brilliant. I’m itching to get my grubby little mitts on their new album, when ever it comes out. Sadly, I do not recollect their support band, but they definitely put on a show and a half!
Next one was in Derwent Bar at the Uni, Who had a good line up, and the gig was put on by BandSoc
Animals in Dangerous Situations. All I could do is laugh, not at them, but with them. Their music was very much like Flight of The Concords, but so explicit and obscene it just got more immature and more funny.
Man is Slapped was one man with a keyboard and a few other assorted insturments. Definitely not my usual style, and I was all ready to be disappointed. Instead I was totally blown away. Loved every second of his set.
And finally, the head liners were Ah Good The Sea. They are very much my style of music. Thoroughly enjoyed it. It was quite odd to think to myself “They’re vaguely reminiscent of Radiohead…” Only for not 5 minutes later the drummer to give up drumming and do a Radiohead cover, before taking his place back behind the drums.
Long story short, I’d recommend seeing the bands mentioned here.