Testing with Spring

Testing with Spring

To improve the quality of your code it is important to thoroughly test your code. Not only using unit tests but also using integration tests. I’ll describe these terms and show examples on how to create tests using JUnit and Spring’s Test library.

Unit Testing

A unit-test is an automated test that tests one single unit-of-work. So, what is this unit-of-work? Its the smallest piece of code that can be distinguished. If you are programming in Java the smallest unit you can test is a single method. So all unit-tests should only test this single unit, and no other dependencies.

Here is an example of a unit-test:

public class CalculatorTest {

	private final Integer TOADD1 = 6;
	private final Integer TOADD2 = 4;
	private final Integer ANSWER = 10;
	
	@Test
	public void testAdd() {
		Calculator calculator = new Calculator();
		
		Integer returnedAnswer = calculator.add(TOADD1, TOADD2);
		
		Assert.assertEquals("The answer of " + TOADD1 + "+" + TOADD2 +
			" should be " + ANSWER + " but was " + returnedAnswer, 
			ANSWER, returnedAnswer);
	}
}

By adding the @Test annotation JUnit will know this is a unit test. When running the code we verify that it correctly adds two values.

Test Driven Development

Test Driven Development (TDD) is very important in modern software development. More and more people and businesses are using this technique to improve their code quality.

What TDD consists of, basically, is a very small development cycle for all your code. You just follow these steps:

  1. Write a unit-test that verifies your usecase
  2. Implement the interfaces you created for step 1
    (can be done quick and dirty, just to get the logic correct)
  3. Run the tests and confirm your code is logically correct
  4. Refactor your code into maintainable, readable, reusable code
  5. Confirm the code still works as designed by running the test(s)

Actually, I don’t write all my tests before the real code, but the process goes hand-in-hand. When writing code I always think about how I’m going to test it, and when the code is done, the test is too, combining step one and two. It speeds the process up a bit, and the code I end up with is almost the same because of the refactor-step.

Integration testing

With unit testing you can verify that the smallest units of work are correct. But this doesn’t give you any guarantees!

A famous example is NASA’s $125 million Mars Orbiter. It crashed when it was about to land on Mars. And why did it crash? Because one component calculated metric units and it feeded this information into another component that was using English units.

Very painfull for NASA, but a great example showing the importance of integration testing. Both NASA-components had been tested a lot, but apparently they neglected to test the components together.

Integration testing with Spring

Most business software in Java uses Spring. This is a framework glueing all your components together and providing dependency injection. This makes it easy to test all the classes and methods, but it makes it a bit harder to test the integration and communication between classes because you depend on the framework for that.

Luckely Spring helps us with a their Spring Test library full of tools that help you creating integration tests.

One thing you need in all integration tests is Springs Context. With Spring Test it is possible to wire some beans and let Spring inject those beans in your unit test. The old(-ish) way to do this is extending org.springframework.test.AbstractDependencyInjectionSpringContextTests or org.springframework.test.AbstractTransactionalSpringContextTests.

If you want to use these classes you need two things:

  • Create a seperate Spring configuration with test-beans (or use your normal Spring config)
  • Override String[] getConfigLocations(), provide it with the location of your Spring configuration.

Now, for all the private fields you have in your testclass Spring will attempt to auto-wire beans on it.

A small example:

public class PersonServiceTest 
	extends AbstractDependencyInjectionSpringContextTests {

	private PersonService personService;

	/**
	 * Integration test for my calculator.
	 * It also calls the calculatorDao which is in the calculatorService.
	 */
	@Test
	public void testAddPerson() {
		
		Person p = ...
		
		personService.add(p);
		
		//Test if the person has been added.

	}
	
	/**
	 * Provide the test with a configuration
	 */
	@Override
	protected String[] getConfigLocations() {
		return new String[] { "my-test-applicationcontext.xml" };
	}
}

Testing with Spring 2.5+

With the introduction of Spring 2.5 they improved the above method. For more flexability and a bit more control over the objects they introduced the SpringJUnit4ClassRunner.

This is how you would use it:

import org.junit.runner.RunWith;
import org.springframework.test.AbstractDependencyInjectionSpringContextTests;
import org.springframework.test.context.ContextConfiguration;
import org.springframework.test.context.junit4.SpringJUnit4ClassRunner;

@RunWith(SpringJUnit4ClassRunner.class)
@ContextConfiguration(locations= { "my-test-applicationcontext.xml" })
public class PersonServiceTest {

	@Autowired
	private PersonService personService;

	/**
	 * Integration test for my calculator.
	 * It also calls the calculatorDao which is in the calculatorService.
	 */
	@Test
	public void testAddPerson() {
		
		Person p = ...
		
		personService.add(p);
		
		//Test if the person has been added.

	}
}

It works the same way as before, but instead of having to override the AbstractDependencyInjectionSpringContextTests you now have a POJO. All the information about Spring and JUnit are placed in annotations on top of you class.

Hopefully I’ll find the time to write another post on mocking, including EasyMock and Mockito.


Feed your curiosity

Feed your curiosity

Curiosity is an emotion related to natural inquisitive behaviour such as exploration, investigation, and learning, evident by observation in human and many animal species.

Source: wikipedia

To me, curiosity is one of the greatest things we as humans have. It feeds you with knowledge and sparks your fantasy, its an emotion that tickles your brain and forces you to explore.

Curiosity isn't limited to humans

In life its vital to search for new things, new limits, new experiences. Always keep asking questions, because with every answer you find, more questions will arise!

At first this sounds a bit depressing, more questions for every answer you get. This doesn’t sound satisfactory, but trust me, it is! Its not the answer that gives you satisfaction, its the new array of questions that give satisfaction! Because these questions feed our curiosity.

It also strikes me that children are very good in asking questions, and they come up with the most amazing questions! I really think this is a good skill, and its a shame we lose this when we get older. Why don’t adults ask these questions? Is it the fear of the “dumb-question”, does it make them look stupid?

Here are some examples of good curious questions:

  • Q: How do blind people know when they’re done wiping toiletpaper?

 

  • A: They can feel it from the drag, and then wipe two times extra (just to be sure)

 

  • Q: If you smoke, and go into a coma. When you wake up, do you crave for a cigarette?

 

  • A: It depends, after 8 days all the nicotine would be out of him/her bloodstream. So the physical chemical craving wouldn’t be there when they wake up. They’ll probably still have a habitual craving though.

 

  • Q: Why don’t our eyelashes grow?

 

  • A: All hair follicles have a certain cycle. The hair grows for a certain time, and then it just drops out. Eyelashes have a short cycle-rate.

 

  • Q: Do fish drink?

 

  • A: It actually depends: Saltwater fish drink, and filter the salt and minerals with their gills. Freshwater fish absorb water with their bodies.

 

  • Q: How many neck-vertebrates does a giraffe have?

 

  • A: The same amount as we have, seven. Even a mouse has seven vertebrates. All mammals have seven vertebrates except the manatee and three-toed sloth (They only have six)

 

  • Q: Can Elephants jump?

 

  • A: No, they can’t! They weigh too much. Also they get very uncomfortable if there is more then one feet of the ground at any time.

 

  • Q: If you die from anti-freeze poisoning, would you be able to do cryopreservation?

 

  • A: ?

 

  • Q: A Dutch question: Waarom moet je bevroren eten altijd “ontdooien”? Dooien is het tegenovergestelde van bevriezen! Dus moet je iets toch dooien in plaats van ontdooien?

 

  • A: ?

If you have curious/weird questions, or know answers to unanswered questions, please drop me a comment!


Atheist look on Christmas

Atheist look on Christmas

Something other then the usual technical posts…
As you might already know, I am an atheist. Yes, in my opinion there is no God, there never was and (probably) never will be.

Atheistic Christmas?

Being an Atheist with Christian friends I get a lot of questions. Recently a friend of mine asked: “Why do you celebrate Christmas when you are an Atheist?”.

This question, to me, is quite simple. First of all, because it is a tradition. I think its a wonderful holiday. Ask around, what do people think about when you ask them about Christmas?

People think about:

  • Christmas trees
  • Snow!
  • Santa Claus
  • Toys, candy and gifts
  • Decorations, lights
  • Christmas dinner with relatives
  • The poor, and less fortunate
  • Christmas songs
  • The Grinch
  • Mistletoe
  • Christmas cards
  • Charles Dickens, A Christmas Carol

All of these things have no connection to the Christian Christmas, except the name “Christ-“.

The birth of Jesus

The date on which we celebrate Christmas is sometimes said to be the birthdate of Christ. But in fact this isn’t true. The date has been borrowed from other holiday’s. Originally people celebrated the Roman winter solstice on the 25th of December. It was probably just convenient to borrow this date.

So instead of saying I celebrate Christmas, I could just say I celebrate midwinter.

Santa Claus

Okay, how about Santa Claus, there is nothing more Christmas then Santa Claus. But again this figure has nothing to do with Christianity. The only thing God and Santa Claus have in common is the beard.

I’m from the Netherlands, and on the 5th of december the old Saint Nicolaas (or Sinterklaas) visits our country. At night he visits all the houses and he brings gifts for all the kids! Does this sound familiar? It should be, he and Santa are the same guy..!

sinterklaas

When New York City was still called New Amsterdam the Dutch tradition took off in America. Slowly evolving (yes, holidays evolve too!) into the Santa Claus we all know today.

And being Dutch I have a huge advantage, we celebrate Sinterklaas AND Santa Claus, getting gifts and candy twice!

But again, a good reason to celebrate Christmas, it is based on a old Dutch tradition, and Santa Claus has nothing to do with Christianity.

Family, friends and relatives

For me, the single most important reason I celebrate Christmas as an Atheist are my family, relatives and friends. Its the time of year, with its long dark days and cold nights, that is perfectly suited for spending time with friends and family.

Its also the perfect time of year to think about your own situation, about the people you know and love, about people who don’t have it as good as you have. Its the time of year of giving and sharing.

That is the most important reason to celebrate Christmas midwinter, winter solstice, late Sinterklaas.

god exits

Evolution…

Finally, I have to get something out of my system about evolution:

Please get over it, evolution exists, there is enough prove. Just because it is called a theory it doesn’t mean you can just throw it out of the Christmas decorated window. For example, did you know gravity is still a theory? It is, first it was known as Newton’s Theory of Gravitation, and after that a guy named Albert Einstein wrote a better version, the General Theory of Relativity. It is accepted that gravity exists and nobody doubts that. Just like gravity, evolution is not just a theory.


VMWare on your phone?

VMWare on your phone?

Recently VMWare, known from its computer virtualization software, has announced they are developing a dual-boot mobile version. This would allow you to run both Windows Mobile and Android on your phone.

But it isn’t going to be a dual-boot you know from your computer, they are planning on running the OS’es at the same time. This would allow you to switch between OS on-the-fly.

  • You want to use a Windows Mobile app? *click*
  • Oh, you want to use something on the Andriod platform? *click*.

I’m very curious how this will work out performance-wise, but the idea itself is great!

Via: computerworld.com.au


Eureqa

Eureqa

I’ve just stumbled across a new program: Eureqa

Its a program, developed by the Cornell Computational Synthesis Laboratory, that can detect equations in sets of data. Its primary goal is to identify the simplest mathematical formulas which could describe the underlying mechanisms that produced the data.

Its best described using their instructional video:

I’ve been playing around with it, for example trying to find a good prediction equation for the Son of Darts competition I blogged about earlier.

The algorithm(s) used in this program are based around “symbolic regression”. It is a form of Genetic Programming (GA) where the computer processes a tree of possibilities recursively searching for the best suited building-blocks.


#songsincode

#songsincode

songsincode

What is #songsincode ?

Last week I discovered a new hype on Twitter. The so-called “#songsincode”. It’s a huge hype under programmers and technical users. The best way to explain is probably by showing an example:

if( door == red ) {
   door.paint(black);
}

This obviously is Paint It Black by the Rolling Stones (if the door is red, paint it black)

My own #songsincode:

Here is a collection of the #songsincode I created and tweeted:

if( silhouetto == man && i.see(silhouetto)) {
   scaramouche.doFandango();
   if(thunderbolt && lightning) {
      me.frightened = true;
   }
}

while(true) {
   ableToCheckout();
}
//Unreachable code:

leave();

switch(random(2)) {
   case 0: feel.partner = null;
      break;
   case 1: feel.onlyFriend = city.of(this, angel);
}

for(mydaddy : oh) {
   whack();
}
jar.insert(whisky);

man.amount = 1;
man.come(love.name());
man.come();
man.go();

life++;
if(life > you && you != me) {
   me.goto(lengths);
   distance(you.eyes);
   if(me.saidTooMuch()) {
      me.setUp(it);
   }
}

for(Person p:people) {
   p.imagine();
}

boolean isLover(String name) {
   if("Billy Jean".equals(name)) {
      return false;
   }
   ...

for(int i = 0;i < 8; i++ ) {
   System.out.println("MMmmmMMmmm");
}
throw new RuntimeException("test dummy");

String bird;
bird = "word";

if(she != lovely && she != wonderfull && she != precious && she.age < 1 ...

Submarine submarine = new Submarine(new Color(255,255,0));
for(Person p:all) {
   submarine.add(p);
}

while( !me.like(mondays) ) {
   tellWhy(me);
}

while(young) {}
//loops forever

if(time == hammer) {
   System.exit(1);
}

if( !women ) {
   cry = false;
}

public static void main(String[] args) {
     this.remove(religion);
}

while(!hasFound) {
   lookFor();
}

if(grass=="green" && girls == "pretty") {
   takeMe(paradiseCity);
}

for(Leaf leaf:leafs) {
   leaf.setColor(new Color(139,69,19));
}
sky.setColor(Color.GRAY);

for(Thing thing:stuff) {
   aintGotNo(thing);
}
complainAboutGod();
for(Part part:bodyparts) {
   gotMy(part);
}
gotMy(life);
gotMy(freedom);
gotMy(life);

{
     final countdown = 10;
}

My favourite:

And here is my all-time favourite (in CSS!!) created by @codepo8:

.clowns{float:left;}
.jokers{float:right};
#me_you{position:fixed;margin:0 auto;width:100%}

I hope you liked them!


Java Generics for Compare

Java Generics for Compare

I’ve been developing with Java 5+ for quite a while now. Not all developers are this lucky, some are still stuck with 1.4… some even with 1.3! But my clients all made the excellent step forward to Java 5 (some even to 6). The problem is, they moved the runtime/JDK but forget to move their developers!

In Java 5 the language brings some good improvements, the for-loop is easy to understand, and almost all the developers are using this by now. The problem starts with generics. There is a part most developers understand, the Collections API. Almost all programmers use lists now as: List instead of a plain old List. This is a good start, but it must not end here! First, I must admit, generics in Java can sometimes be hard and confusing (when using <? extends X> and <? super X>). So I'm not going to talk about any of this 'hard stuff'. Its the use of 'easy' generics that can our lifes so much easier.

For example the piece of code below:

public class LabelPlaceholderComparator implements Comparator { 

    /**{@inheritDoc */
    public int compare(Object o1, Object o2) {
        LabelPlaceholder p1 = (LabelPlaceholder) o1;
        LabelPlaceholder p2 = (LabelPlaceholder) o2;
        return p1.getLabel().compareTo(p2.getLabel());
    }
}

Of course, there seems to be not much wrong with the code, I see it all the time. Yes, the code breaks if you put something else in the comparator, but hey… the Javadoc says it only accepts LabelPlaceholders! So lets use this code:

List holders = fillList();
Collections.sort(holders, new LabelPlaceholderComparator());

Done! Its working and no problems right? Not quite, your IDE (Eclipse in my case) complains about this code.
For example Eclipse says:

Type safety: The expression of type LabelPlaceholderComparator needs unchecked conversion to conform to Comparator<? super T>

At this point, most programmers at the company I work for now will just ignore this warning. They might even add:
@SuppressWarnings(“unchecked”)

What a shame… Lets just examine this warning, what is Eclipse trying to tell us here? The compiler doesn’t know we created the Comparator with only LabelPlaceholders in mind. But the compiler does know (with generics) that the List only contains LabelPlaceholders. So the warning is (in understandable English):

I’ve got a list here of T (LabelPlaceholders) and a Comparator for Objects, this can go wrong! I’d rather have a specific Comparator for this job. Do you have one for me?

The solution to this problem is very simple, but most neglect to use it:

public class LabelPlaceholderComparator implements Comparator<LabelPlaceholder> { 

    /**{@inheritDoc */
    public int compare(LabelPlaceholder p1, LabelPlaceholder p2) {
        return p1.getLabel().compareTo(p2.getLabel());
    }
}

As you can see, the code is much smaller. The interface is now generified, it knows we are going to compare LabelPlaceholders now, nothing more, nothing less. Also, we don’t have to cast anymore, because of the generics you can’t put anything else in there.

So, lets go to the conclusion: Why is the latter code better code?

  1. As you can see, the code is smaller!
  2. There are no casts, the code is safer (no ClassCastException or eleborate class checks)
  3. If somebody uses your code, he/she knows what kind of objects the Comparator can handle. You don’t have to read the Javadoc or the code to see what it does.

Throughout the projects I encounter I keep finding examples of places where generics would have made the code smaller/safer/more understandable. For some reason the programmers still only use generics on collections. So, even though generics aren’t perfect, please use them where/when you can, it’ll always add clarity to the code, and most of the time it’ll also make your code safer, and in some cases the code gets smaller because you can leave away casts and class-checks.

Don’t ever let me see public int compare(Object o1, Object o2); again!

(You see, it is possible for me to have a discussion about Java generics without mentioning reified generics!)


Son Of Darts

Son Of Darts

Another thing I’ve been very busy with lately is AZsPCs (Al Zimmermanns Programming Competition). The current contest is called Son of Darts.

The idea behind these contests are that they are easy to grasp, but very hard to master.

Lets take three darts. You have to throw them to a dartboard which is divided into 4 regions. For example, the values on these regions are: 1,2,4,6.
The first question is: What is the lowest value you can’t throw with these three darts?

This is easy to calculate:
Can we throw one? Yes: 1 dart in the 1
Can we throw two? Yes: 1 dart in the 2, or 2 darts in the 1
etc etc
Can we throw nine? Yes: 6,2,1
Can we throw ten? Yes: 6,4
Can we throw eleven? Yes: 6,4,1
Can we throw twelve? Yes: 6,6
Can we throw thirteen? Yes: 6,6,1
Can we throw fourteen? Yes: 6,6,2
Can we throw fifteen? Err… no, sorry…

So the score is: 15 points.

The main question: Can you think of better values for the regions of the dartboard to get a higher topscore??

This is what the competition is about. But not only for a dartboard consisting of 4 regions, but up to 40 regions. And not only for three darts, but also 4, 5 and even 6 darts.

If you can create a good solver its pretty easy to bruteforce up to a certain point, but the problem is, you quickly get more and more options for which you have to check the scores… It is an exponential function…!

Actually, this is not a new puzzle. Its been around of quite a long time. But its more commenly known as the local postage stamp problem (LPSP). Formulated just a little bit different, instead of a dartboard with regions you have a postcard with room for H stamps. What is the lowest value you can’t create with stamps Nh? Also check out Wolfram’s description of the problem.

This problem has been proven to be NP-hard, so bruteforcing won’t be an option, you’ll need to use something different. Put on your thinking-caps and create some good innovative heuristics.


Quine - McCluskey

Quine - McCluskey

About a week ago I had a discussion with a fellow programmer about some boolean logic. We had three parameters, something like:

  1. personHasInsurence (A)
  2. personNeedsInsurence (B)
  3. personIsKnownAtThisAgency (C)

We also had two particulair cases for an insurance page:

Case 1:
Person has insurence and isn’t yet known at this agency

Case 2:
Person doesn’t have insurence, needs insurence and is known at this agency

Case 3:
Person doesn’t have insurence, doesn’t need insurence and is known at this agency

So the view-logic was a bit complex:

if( (A && !C) || (!A && B && C) || (!A && !B && C ) ) {
    showPage();
}

Then I remebered something I learned at school some time ago. So called karnaugh maps. I’ve completely forgotten how to use them, but I knew it was possible to calculate the shortest form to comply to the logic rules. When looking further I found the so called “Quine McCluskey“-algorithm, and I decided to implement it (just to learn how it works).

Quine - McCluskey algorithm

First of, lets go through a couple of terms.

Minterm: A small boolean function which has all the different input variables, once. So for example, a minterm using the above variables would be: ABC (A and B and C), or A’BC (not A and B and C).

The first thing you do using this algorithm is that you find so called “prime implicants”. An implicant is a combination of one (or more) minterms, and a prime implicant is a implicant which can’t be combined with other implicants (for more details, read the wikipage with examples)!

After combining all the minterm of your case(s), you’ll end up with a “prime implicant chart”. This is a chart with all the prime implicants and the fields they cover. Sometimes its easy to spot “essential prime implicants”. That is, implicants which are unique in covering a field. You have to use these implicants in the final logic.

When you have multiple options left to combine to cover all the fields, you can use Petrick’s Method to select the best/smallest option.

Using the above example, if you minimize, you’ll come down to:

if((!A && C) || (A && !C)) {
    showPage();
}

The algorithm is pretty fun to program, and its a bit different from most algorithms I’ve seen lately!

And if you need something even faster, try out Espresso!

ps. I love browsing this page: List of algorithms
But OTOH, its kind of depressing I still have soo much to learn.


Corewars - Brainf*ck

Corewars - Brainf*ck

I’ve implemented a Brainfuck interpreter!

Yes, you heard it right, Brainfuck (BF).
BF is an esoteric programming language. More information on BF can be found here.

The language itself is pretty simple, and most of it was implemented rather quickly in Redcode. The only big problem was navigating back to the correct closing brackets in a loop. This is now solved by counting the amount of open/close brackets in between.

So here is the code:

;----------------------------------------------
;redcode-94nop 
;name Brainfuck Interpreter (v0.3) 
;author Roy van Rijn 
;strategy Brainfuck Interpreter with self-reproduction program (a quine) 
;strategy It takes 7244366 cycles (runs slow!)
;assert 1 


LT      equ     60 ;<
GT      equ     62 ;> 
INC     equ     43 ;+ 
DEC     equ     45 ;- 
OUT     equ     46 ;. 
IN      equ     44 ;, 
OP      equ     91 ;[ 
CL      equ     93 ;] 


lt      equ     dat LT  , cLT-START 
gt      equ     dat GT  , cGT-START 
inc     equ     dat INC , cINC-START 
dec     equ     dat DEC , cDEC-START 
out     equ     dat OUT , cOUT-START 
in      equ     dat IN  , cIN-START 
op      equ     dat OP  , cOP-START 
cl      equ     dat CL  , cCL-START 


;Use switch-table 
cINC    add     #2              , @PTR          ;add 2 min 1 
cDEC    sub     #1              , @PTR          ;min 1 


START   mov.b   }PTR            , #0 
       jmp     @-1 


cLT     jmp     START           , PTR 


cOUT    mov.b   @PTR            , <6000         ;sts.b  @PTR 
       jmp     START 
cIN     mov.b   }INPUT          , @PTR          ;now using INPUT-table instead or streams 
       jmp     START 


;Optimize by using a stack? remembering the layer+position? 
cOP     jmn     START           , @PTR 
opCheck sne.ab  *PTR            , #OP 
       add     #1              , CNT1 ;Count nested brackets 
       seq.ab  }PTR            , #CL 
       jmp     opCheck 
CNT1    djn.b   opCheck         , #1 
       jmp     START           , >CNT1 


cCL     jmz     START           , @PTR 
       nop     {PTR            , >CNT2 
clCheck sne.ab  {PTR            , #CL 
       add     #1              , CNT2 ;Count nested brackets 
       seq.ab  *PTR            , #OP 
       jmp     clCheck 
CNT2    djn.b   clCheck         , #0 
       jmp     START 


;Used to mimic keypresses (when not using exmars_streams) 
INPUT   dat     0               , -1 


PROGRAM 


;Brainfuck Quine, unsure who wrote the original.... (not me anyway!) 


dec 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
inc 
gt 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
gt 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
inc 
inc
 gt 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
inc 
gt 
inc 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
gt 
gt 
gt 
gt 
inc 
gt 
inc 
gt 
gt 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
inc 
gt 
gt 
inc 
gt 
inc 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
gt 
gt 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
inc 
inc 
inc 
gt 
gt 
inc 
op 
op 
gt 
gt 
inc 
op 
gt 
cl 
inc
gt 
inc 
op 
lt 
cl 
lt 
dec 
cl 
gt 
gt 
op 
gt 
cl 
lt 
inc 
lt 
inc 
inc 
inc
op 
lt 
cl 
lt 
lt 
inc 
cl 
gt 
gt 
inc 
op 
gt 
cl 
inc 
inc 
inc 
op 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
gt 
inc 
inc 
op 
dec 
lt 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
gt 
cl 
lt 
out 
lt 
dec 
lt 
cl 


EOF     dat     0               , -10           ; Halt 
PTR     dat     #PROGRAM        , #1            ; A: Execution pointer, B: Data pointer 


end START 


;Translated Brainfuck "Hello World" program 
; 
;The original is: 
;++++++++++[>+++++++>++++++++++>+++>+<<<<-] 
;>++.>+.+++++++..+++.>++.<<+++++++++++++++.> 
;.+++.------.--------.>+.>. 


inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
op 
gt 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
gt 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
gt 
inc 
inc 
inc 
gt 
inc 
lt 
lt 
lt 
lt 
dec 
cl 
gt 
inc 
inc 
out 
gt 
inc 
out 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
out 
out 
inc 
inc 
inc 
out 
gt 
inc 
inc 
out 
lt 
lt 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
inc 
out 
gt 
out 
inc 
inc 
inc 
out 
dec 
dec 
dec 
dec 
dec 
dec 
out 
dec 
dec 
dec 
dec 
dec 
dec 
dec 
dec 
out 
gt 
inc 
out 
gt 
out 


EOF     dat     0               , -10           ; Halt 
PTR     dat     #PROGRAM        , #1            ; A: Execution pointer, B: Data pointer 


end START

Corewars - SUBLEQ interpreter

Corewars - SUBLEQ interpreter

In my previous blogpost I talked about Corewars and the Redcode language. But instead of playing the game, you can do a lot more with the programming language. John Metcalf posted a blog about OISC (One Instruction Set Computers). He decided to implement the RSSB algorithm, so I took on the challenge of implementing SUBLEQ, another single instruction set computer.

And here is the result:

;-----------------------------------------------
;redcode-94odd
;name SUBLEQ Hello World
;author Roy van Rijn
;assert 1
;-----------------------------------------------
;Implementation of the OISC SUBLEQ interpreter.
; All instructions take 3 lines:
; dat A,0
; dat B,0
; dat C,0
;
; The interpreter works as following:
;
; Substract A from B
; If B is less or equal to zero jump to C
; Else go to the next instruction (+3)
;
; If the jump is to HALT (-1) the program will halt
; If the substraction is OUT (-2) the program will output the amount substracted
;-----------------------------------------------
HALT   equ -1
OUT    equ -2

;Pointers used by program:
EQ     dat PROGRAM-1      , PROGRAM
PTR    dat PROGRAM        , PROGRAM+1
RESETV dat PROGRAM-SUBSTR , PROGRAM-SUBSTR ;reset values
NEXTV  dat #3             , #3

;Print to command line:
PRINT  mov.ab *SUBSTR     , #0
       mov.b  -1          , <1000 ;sts.b -1,0 for output

;Reset to absolute values:
NEXT   add.f NEXTV        , PTR
RESET  mov.f RESETV       , SUBSTR

;Main logic:
START  add.a  *PTR        , SUBSTR
       add.ab >PTR        , SUBSTR
       mov.a  @PTR        , NEWPTR

;Check if output is OUT, print and go to next instruction:
       mov.a  <PTR        , 1
       sne.ab #0          , #OUT
       jmp    PRINT

;Substract and determine if the value <= 0
SUBSTR sub.a  PROGRAM     , PROGRAM
       slt.a  #CORESIZE/2 , @-1
       jmn.ba NEXT        , @-2

;Jump to new address:
NEWPTR mov.ab #0          , #0
       mov.f  NEWPTR      , PTR
       add.f  EQ          , PTR
       seq.ab NEWPTR      , #HALT

;Check for HALT (jump to DAT-PROGRAM)
       jmp RESET

LABEL
PROGRAM

;-----------------------------------------------
;Translated version of the Hello World program from:
;http://mozaika.com.au/oleg/subleq/

dat A-LABEL,0
dat A-LABEL,0
dat 3,0
dat p-LABEL,0
dat Z-LABEL ,0
dat 6,0

dat Z-LABEL ,0
dat A-LABEL ,0
dat 9,0

dat Z-LABEL ,0

dat Z-LABEL ,0
dat A-LABEL,0

A dat PROGRAM ,0
dat OUT ,0
dat 15,0

dat m1-LABEL,0
dat p-LABEL,0
dat 18,0

dat A-LABEL ,0
dat A-LABEL ,0
dat 21,0

dat E-LABEL ,0
dat Z-LABEL ,0
dat 24,0

dat Z-LABEL ,0
dat A-LABEL ,0
dat 27,0

dat Z-LABEL,0
dat Z-LABEL,0
dat 30,0

dat b-LABEL,0
dat b-LABEL,0
dat 33,0

dat p-LABEL,0
dat Z-LABEL,0
dat 36,0

dat Z-LABEL ,0
dat b-LABEL,0
dat 39,0

dat Z-LABEL,0
dat Z-LABEL,0
dat 42,0

dat E-LABEL,0
dat b-LABEL,0
dat 48,0 ;?+3

dat Z-LABEL ,0
dat Z-LABEL,0
dat 51,0 ;?+3

dat p-LABEL,0
dat A-LABEL,0
dat 54,0 ;?+3

dat Z-LABEL ,0
dat Z-LABEL ,0
dat 0,0

dat 0 ,0
dat 0 ,0
dat -1,0

;data
p dat H-LABEL,0
Z dat 0,0
m1 dat -1,0
b dat 0,0
H dat 72,0 ;:H
dat 101,0 ; e
dat 108,0 ; l
dat 108,0 ; l
dat 111,0 ; o
dat 32,0 ; space
dat 87,0 ; W
dat 111,0 ; o
dat 114,0 ; r
dat 108,0 ; l
dat 100,0 ; d
E dat E-LABEL,0

end START
;-----------------------------------------------

Corewars - An Introduction to Hostile Programming

Corewars - An Introduction to Hostile Programming

Corewar is a game from the 1980’s, played between computer programs written in Redcode, a language similar to assembly. The programmers design their battle programs to remove opponents from the memory of the MARS virtual computer by any means possible.

Some of the simpler techniques include blindly overwriting memory, searching for the opponent or spawning off new processes. These are commonly known as stone, scissors, paper after the popular playground game. Stone usually wins against scissors, scissors normally defeat paper, and paper mostly beats stone.

Here’s an example of a typical Corewar program:

org   wipe
    
step  equ 5
first equ bomb-10
    
    bomb:mov.i #1,       -1
    
    ptr: sub   #step,    #first
    wipe:jmz.f ptr,      @ptr
    
mov   bomb,     >ptr
djn.f wipe,     {ptr-5
    
end

This simple example of scissors once held a 20 point lead over it’s rivals. The first instruction is never executed, it’s the bomb used to overwrite opponents. The next two instructions form a loop which looks through memory for an opponent, and the final two instructions actually overwrite it.

Corewar is still going strong, and celebrates it’s 25th anniversary in 2009. If you’d like to discover more about Corewar, here are the top resources:

  • The Beginner’s Guide to Redcode will teach you the language of Corewar
  • pMARS is a portable implementation of the Corewar virtual machine
  • Corewar Tutorials exist on virtually every aspect of the game
  • Koenigstuhl is an archive of thousands of published Corewar programs
  • SAL organises a number of on-going king of the hill tournaments
  • sfghoul and impomatic report the latest Corewar news on their blogs
  • #corewars is the official Corewar discussion channel, hosted by irc.freenode.net

What are your experiences with Corewar, have you ever had any success?