DDevelopment & Design

Hamming Error Correction with Kotlin – part 2

In this article, we continue where we left off and focus solely on error detection for Hamming codes.

https://touk.pl/blog/2017/10/17/hamming-error-correction-with-kotlin-part-1/

Error Correction

Utilizing Hamming(7,4) encoding allows us to detect double-bit errors and even correct single-bit ones!

During the encoding, we only add parity bits, so the happy path decoding scenario involves stripping the message from the parity bits which reside at known indexes (1,2,4…n, 2n):

fun stripHammingMetadata(input: EncodedString): BinaryString {
    return input.value.asSequence()
      .filterIndexed { i, _ -> (i + 1).isPowerOfTwo().not() }
      .joinToString("")
      .let(::BinaryString)
}

This is rarely the case because since we made effort to calculate parity bits, we want to leverage them first.

The codeword validation is quite intuitive if you already understand the encoding process. We simply need to recalculate all parity bits and do the parity check (check if those values match what’s in the message):

private fun indexesOfInvalidParityBits(input: EncodedString): List {
    fun toValidationResult(it: Int, input: EncodedString): Pair =
      helper.parityIndicesSequence(it - 1, input.length)
        .map { v -> input[v].toBinaryInt() }
        .fold(input[it - 1].toBinaryInt()) { a, b -> a xor b }
        .let { r -> it to (r == 0) }

    return generateSequence(1) { it * 2 }
      .takeWhile { it < input.length }
      .map { toValidationResult(it, input) }
      .filter { !it.second }
      .map { it.first }
      .toList()
}

If they all match, then the codeword does not contain any errors:

override fun isValid(codeWord: EncodedString) =
  indexesOfInvalidParityBits(input).isEmpty()

Now, when we already know if the message was transmitted incorrectly, we can request the sender to retransmit the message… or try to correct it ourselves.

Finding the distorted bit is as easy as summing the indexes of invalid parity bits – the result is the index of the faulty one. In order to correct the message, we can simply flip the bit:

override fun decode(codeWord: EncodedString): BinaryString =
  indexesOfInvalidParityBits(codeWord).let { result ->
      when (result.isEmpty()) {
          true -> codeWord
          false -> codeWord.withBitFlippedAt(result.sum() - 1)
      }.let { extractor.stripHammingMetadata(it) }
  }

We flip the bit using an extension:

private fun EncodedString.withBitFlippedAt(index: Int) = this[index].toString().toInt()
  .let { this.value.replaceRange(index, index + 1, ((it + 1) % 2).toString()) }
  .let(::EncodedString)

We can see that it works by writing a home-made property test:

@Test
fun shouldEncodeAndDecodeWithSingleBitErrors() = repeat(10000) {
    randomMessage().let {
        assertThat(it).isEqualTo(decoder.decode(encoder.encode(it)
          .withBitFlippedAt(rand.nextInt(it.length))))
    }
}

Unfortunately, the Hamming (7,4) does not distinguish between codewords containing one or two distorted bits. If you try to correct the two-bit error, the result will be incorrect.

Disappointing, right? This is what drove the decision to make use of an additional parity bit and create the Hamming (8,4).

Conclusion

We’ve seen how the error correction for Hamming codes look like and went through the extensive off-by-one-error workout.

Code snippets can be found on GitHub.

— Previous article

Hamming Error Correction with Kotlin - part 1

Next article —

Karaf configuration as Groovy file

You May Also Like
DDevelopment & Design

33rd Degree day 1 review

33rd Degree is over. After the one last year, my expectations were very high, but Grzegorz Duda once again proved he's more than able to deliver. With up to five tracks (most of the time: four presentations + one workshop), and ~650 attendees,  there was a lot to see and a lot to do, thus everyone will probably have a little bit different story to tell. Here is mine.

Twitter: From Ruby on Rails to the JVM

Raffi Krikorian talking about Twitter and JVM
The conference started with  Raffi Krikorian from Twitter, talking about their use for JVM. Twitter was build with Ruby but with their performance management a lot of the backend was moved to Scala, Java and Closure. Raffi noted, that for Ruby programmers Scala was easier to grasp than Java, more natural, which is quite interesting considering how many PHP guys move to Ruby these days because of the same reasons. Perhaps the path of learning Jacek Laskowski once described (Java -> Groovy -> Scala/Closure) may be on par with PHP -> Ruby -> Scala. It definitely feels like Scala is the holy grail of languages these days.

Raffi also noted, that while JVM delivered speed and a concurrency model to Twitter stack, it wasn't enough, and they've build/customized their own Garbage Collector. My guess is that Scala/Closure could also be used because of a nice concurrency solutions (STM, immutables and so on).

Raffi pointed out, that with the scale of Twitter, you easily get 3 million hits per second, and that means you probably have 3 edge cases every second. I'd love to learn listen to lessons they've learned from this.

 

Complexity of Complexity


The second keynote of the first day, was Ken Sipe talking about complexity. He made a good point that there is a difference between complex and complicated, and that we often recognize things as complex only because we are less familiar with them. This goes more interesting the moment you realize that the shift in last 20 years of computer languages, from the "Less is more" paradigm (think Java, ASM) to "More is better" (Groovy/Scala/Closure), where you have more complex language, with more powerful and less verbose syntax, that is actually not more complicated, it just looks less familiar.

So while 10 years ago, I really liked Java as a general purpose language for it's small set of rules that could get you everywhere, it turned out that to do most of the real world stuff, a lot of code had to be written. The situation got better thanks to libraries/frameworks and so on, but it's just patching. New languages have a lot of stuff build into, which makes their set of rules and syntax much more complex, but once you get familiar, the real world usage is simple, faster, better, with less traps laying around, waiting for you to fall.

Ken also pointed out, that while Entity Service Bus looks really simple on diagrams, it's usually very difficult and complicated to use from the perspective of the programmer. And that's probably why it gets chosen so often - the guys selling/buying it, look no deeper than on the diagram.

 

Pointy haired bosses and pragmatic programmers: Facts and Fallacies of Software Development

Venkat Subramaniam with Dima
Dima got lucky. Or maybe not.

Venkat Subramaniam is the kind of a speaker that talk about very simple things in a way, which makes everyone either laugh or reflect. Yes, he is a showman, but hey, that's actually good, because even if you know the subject quite well, his talks are still very entertaining.
This talk was very generic (here's my thesis: the longer the title, the more generic the talk will be), interesting and fun, but at the end I'm unable to see anything new I'd have learned, apart from the distinction between Dynamic vs Static and Strong vs Weak typing, which I've seen the last year, but managed to forgot. This may be a very interesting argument for all those who are afraid of Groovy/Ruby, after bad experience with PHP or Perl.

Build Trust in Your Build to Deployment Flow!


Frederic Simon talked about DevOps and deployment, and that was a miss in my  schedule, because of two reasons. First, the talk was aimed at DevOps specifically, and while the subject is trendy lately, without big-scale problems, deployment is a process I usually set up and forget about. It just works, mostly because I only have to deal with one (current) project at a time. 
Not much love for Dart.
Second, while Frederic has a fabulous accent and a nice, loud voice, he tends to start each sentence loud and fade the sound at the end. This, together with mics failing him badly, made half of the presentation hard to grasp unless you were sitting in the first row.
I'm not saying the presentation was bad, far from it, it just clearly wasn't for me.
I've left a few minutes before the end, to see how many people came to Dart presentation by Mike West. I was kind of interested, since I'm following Warsaw Google Technology User Group and heard a few voices about why I should pay attentions to that new Google language. As you can see from the picture on the right, the majority tends to disagree with that opinion.

 

Non blocking, composable reactive web programming with Iteratees

Sadek Drobi's talk about Iteratees in Play 2.0 was very refreshing. Perhaps because I've never used Play before, but the presentation was flawless, with well explained problems, concepts and solutions.
Sadek started with a reflection on how much CPU we waste waiting for IO in web development, then moved to Play's Iteratees, to explain the concept and implementation, which while very different from the that overused Request/Servlet model, looked really nice and simple. I'm not sure though, how much the problem is present when you have a simple service, serving static content before your app server. Think apache (and faster) before tomcat. That won't fix the upload/download issue though, which is beautifully solved in Play 2.0

The Future of the Java Platform: Java SE 8 & Beyond


Simon Ritter is an intriguing fellow. If you take a glance at his work history (AT&T UNIX System Labs -> Novell -> Sun -> Oracle), you can easily see, he's a heavy weight player.
His presentation was rich in content, no corpo-bullshit. He started with a bit of history of JCP and how it looks like right now, then moved to the most interesting stuff, changes. Now I could give you a summary here, but there is really no point: you'd be much better taking look at the slides. There are only 48 of them, but everything is self-explanatory.
While I'm very disappointed with the speed of changes, especially when compared to the C# world, I'm glad with the direction and the fact that they finally want to BREAK the compatibility with the broken stuff (generics, etc.).  Moving to other languages I guess I won't be the one to scream "My god, finally!" somewhere in 2017, though. All the changes together look very promising, it's just that I'd like to have them like... now? Next year max, not near the heat death of the universe.

Simon also revealed one of the great mysteries of Java, to me:
The original idea behind JNI was to make it hard to write, to discourage people form using it.
On a side note, did you know Tegra3 has actually 5 cores? You use 4 of them, and then switch to the other one, when you battery gets low.

BOF: Spring and CloudFoundry


Having most of my folks moved to see "Typesafe stack 2.0" fabulously organized by Rafał Wasilewski and  Wojtek Erbetowski (with both of whom I had a pleasure to travel to the conference) and knowing it will be recorded, I've decided to see what Josh Long has to say about CloudFoundry, a subject I find very intriguing after the de facto fiasco of Google App Engine.

The audience was small but vibrant, mostly users of Amazon EC2, and while it turned out that Josh didn't have much, with pricing and details not yet public, the fact that Spring Source has already created their own competition (Could Foundry is both an Open Source app and a service), takes a lot from my anxiety.

For the review of the second day of the conference, go here.
DDevelopment & Design

Grails session timeout without XML

This article shows clean, non hacky way of configuring featureful event listeners for Grails application servlet context. Feat. HttpSessionListener as a Spring bean example with session timeout depending on whether user account is premium or not.

Common approaches

Speaking of session timeout config in Grails, a default approach is to install templates with a command. This way we got direct access to web.xml file. Also more unnecessary files are created. Despite that unnecessary files are unnecessary, we should also remember some other common knowledge: XML is not for humans.

Another, a bit more hacky, way is to create mysterious scripts/_Events.groovy file. Inside of which, by using not less enigmatic closure: eventWebXmlEnd = { filename -> ... }, we can parse and hack into web.xml with a help of XmlSlurper.
Even though lot of Grails plugins do it similar way, still it’s not really straightforward, is it? Besides, where’s the IDE support? Hello!?

Examples of both above ways can be seen on StackOverflow.

Simpler and cleaner way

By adding just a single line to the already generated init closure we have it done:
class BootStrap {


    def init = { servletContext ->    

        servletContext.addListener(OurListenerClass)    

    }    

}

Allrighty, this is enough to avoid XML. Sweets are served after the main course though :)

Listener as a Spring bean

Let us assume we have a requirement. Set a longer session timeout for premium user account.
Users are authenticated upon session creation through SSO.

To easy meet the requirements just instantiate the CustomTimeoutSessionListener as Spring bean at resources.groovy. We also going to need some source of the user custom session timeout. Let say a ConfigService.
beans = {    

    customTimeoutSessionListener(CustomTimeoutSessionListener) {    

        configService = ref('configService')    

    }    

}

With such approach BootStrap.groovy has to by slightly modified. To keep control on listener instantation, instead of passing listener class type, Spring bean is injected by Grails and the instance passed:
class BootStrap {


    def customTimeoutSessionListener


    def init = { servletContext ->    

        servletContext.addListener(customTimeoutSessionListener)

    }    

}

An example CustomTimeoutSessionListener implementation can look like:
import javax.servlet.http.HttpSessionEvent    

import javax.servlet.http.HttpSessionListener    

import your.app.ConfigService    


class CustomTimeoutSessionListener implements HttpSessionListener {    


    ConfigService configService


    @Override    

    void sessionCreated(HttpSessionEvent httpSessionEvent) {    

        httpSessionEvent.session.maxInactiveInterval = configService.sessionTimeoutSeconds

    }    


    @Override    

    void sessionDestroyed(HttpSessionEvent httpSessionEvent) { /* nothing to implement */ }    

}
Having at hand all power of the Spring IoC this is surely a good place to load some persisted user’s account stuff into the session or to notify any other adequate bean about user presence.

Wait, what about the user context?

Honest answer is: that depends on your case. Yet here’s an example of getSessionTimeoutMinutes() implementation using Spring Security:
import org.springframework.security.core.context.SecurityContextHolder    


class ConfigService {


    static final int 3H = 3 * 60 * 60

    static final int QUARTER = 15 * 60


    int getSessionTimeoutSeconds() {    


        String username = SecurityContextHolder.context?.authentication?.principal    

        def account = Account.findByUsername(username)    


        return account?.premium ? 3H : QUARTER

    }    

}
This example is simplified. Does not contain much of defensive programming. Just an assumption that principal is already set and is a String - unique username. Thanks to Grails convention our ConfigService is transactional so the Account domain class can use GORM dynamic finder.
OK, config fetching implementation details are out of scope here anyway. You can get, load, fetch, obtain from wherever you like to. Domain persistence, principal object, role config, external file and so on...

Any gotchas?

There is one. When running grails test command, servletContext comes as some mocked class instance without addListener method. Thus we going to have a MissingMethodException when running tests :(

Solution is typical:
def init = { servletContext ->

    if (Environment.current != Environment.TEST) {    

        servletContext.addListener(customTimeoutSessionListener)    

    }    

}
An unnecessary obstacle if you ask me. Should I submit a Jira issue about that?

TL;DR

Just implement a HttpSessionListener. Create a Spring bean of the listener. Inject it into BootStrap.groovy and call servletContext.addListener(injectedListener).
DDevelopment & Design

micro-burn has Trello integration

After a few long evenings I've finally integrated micro-burn with Trello. All you need to run it for your Trello board is to write short configuration and run fat jar. It renders burndown chart visualising progress of cards on your board.You can specif...After a few long evenings I've finally integrated micro-burn with Trello. All you need to run it for your Trello board is to write short configuration and run fat jar. It renders burndown chart visualising progress of cards on your board.