3 May , 2008

Permalink 22:24 UTC, by Fernando J. Pereda, 725 words, 339 views   English (US)
Categories: Gentoo

On cooperating and paludis vulnerability

A serious security issue in paludis was brought to my attention recently, and I feel I should make you all aware. Apparently someone, with root access to a machine, can gain root access by installing or editing paludis config files.

For those interested, this is how it happened (times are GMT+1):

22:34 <@ferdy> bonsaikitten: can you give me any details regarding that
 security bug in paludis?
22:35 <+bonsaikitten> ferdy: it's so obvious you should have found it already
22:37 <@ferdy> bonsaikitten: I should, but I probably haven't
22:37 <+bonsaikitten> ferdy: well, as I am a moron I'm unable to coherently explain :)
22:37 <@ferdy> bonsaikitten: I mean, depends on whether we are talking about
a real security issue or about something we should document to avoid people
shooting themselves in the foot
22:39 <@ferdy> bonsaikitten: is that all you are going to tell me?
22:39 <+bonsaikitten> ferdy: come on, it's obvious. You're supposed to be smart ...
22:39 * bonsaikitten is not in a mood to explain
22:40 <@ferdy> bonsaikitten: you aren't really talking about the paludisbuild issue, are you?
22:41 <+bonsaikitten> mmh no, that's a different one
22:41 <@ferdy> k
22:41 <@ferdy> bonsaikitten: what are we talking about?
22:42 <@ferdy> bonsaikitten: you don't need to explain it... just say, in general 
terms, what the issue is
22:50 <@ferdy> bonsaikitten: so? care to give any useful hint?
22:50 <+bonsaikitten> ferdy: doesn't happen in portage compatibility mode
22:51 <+bonsaikitten> but I blame the vodka, hard to explain when *burp* *giggle*
22:52 <@ferdy> bonsaikitten: what's the impact?
22:53 <+bonsaikitten> ferdy: depends on how annoying the other person is
22:54 <+bonsaikitten> ferdy: worst case random file modification
22:58 <@ferdy> bonsaikitten: and we already agreed that we aren't talking about
the paludisbuild issue, right?
22:59 <@ferdy> bonsaikitten: if we aren't, I'll need more hints....
23:05 <@ferdy> bonsaikitten: can I get an attack vector?
23:05 <@ferdy> that shouldn't need lots of explaining... I can figure out that
part myself
23:19 <@ferdy> bonsaikitten: have you got that attack vector for me?
23:24 <+bonsaikitten> ferdy: look at configuration files, maybe you notice that
there's some exquisit code execution possible there
23:29 <@ferdy> bonsaikitten: you mean those config files that only root can
edit? I must be missing something here
23:29 <+bonsaikitten> ferdy: you are :)
23:29 <+bonsaikitten> not much, and it's basically the same flaw bashrc is
for portage
23:29 <+bonsaikitten> only that bashrc is config_protect'ed ...
23:30 <@ferdy> bonsaikitten: but for a package to clover those files, it must be
in a repo root added, right?
23:31 <+bonsaikitten> someone in the package mangler group, but yes
23:35 <@ferdy> bonsaikitten: but if you can change those files in the first place,
why clover them by adding a malicious repo with a malicious package that changes
those files?
23:35 <+bonsaikitten> ferdy: because it's very subtle
23:36 <@ferdy> moreover, if you can already do that, why not just make the
package install whatever backdoor you want?
23:37 <@ferdy> I mean, it is subtle, but why would anyone go the 'convoluted'
route? he is already able to edit those files (since he had to add that repo)
23:38 <+bonsaikitten> 'cause only paludis is affected and you will find it very
hard to trace
23:38 <+bonsaikitten> that makes it so tempting ...
23:40 <+bonsaikitten> just don't be surprised if it suddenly unmerges itself :)
23:41 <@ferdy> yeah... well...
23:41 <@ferdy> bonsaikitten: mind if I disclose this vulnerability in
 planet.gentoo.org?
23:42 <+bonsaikitten> go ahead
23:42 <@ferdy> ta
23:42 <+bonsaikitten> 't is even on the features page of the package mangler :)

This is a good lesson to learn today:

If you can edit files owned by root in a machine, you can get root access to that machine.

So the bottom line is: There is no vulnerability, if you can mangle paludis config files, you are already root so you don't need to edit a file to run any command you want. Another lesson one can learn by reading that log is how to be really cooperative.

Ah, and before someone with a need to use cheap psychology asks, the intention of this blag post is to stop the FUD.

- ferdy

28 April, 2008

Permalink 08:07 UTC, by Fernando J. Pereda, 140 words, 316 views   English (US)
Categories: Gentoo, Rants

When you think you've seen everything...

...you get up, fire your mail client just to find:

https://bugs.gentoo.org/show_bug.cgi?id=64840
https://bugs.gentoo.org/show_bug.cgi?id=168573
https://bugs.gentoo.org/show_bug.cgi?id=161368

Please take the time to read those 'Excerpts', they are really enlightening. Politics is so much fun.

Some facts:

  • All of them work in Paludis
  • Some of them have been vocal against how #gentoo and forums.gentoo.org are managed and its politics.
  • Using the image I posted yesterday as an avatar is one of the reasons one of them got the boot.

I wonder who is going to be next. I also wonder who 'started' the process. It is difficult to know, because the bug is restricted ( https://bugs.gentoo.org/show_bug.cgi?id=216219 ).

Way to go Gentoo. No love for you today.

- ferdy

27 April, 2008

Permalink 19:39 UTC, by Fernando J. Pereda, 36 words, 272 views   English (US)
Categories: Gentoo, Rants

Doing It Wrong

I hear this image got someone a Developer Relations complain. Way to go, Gentoo. Way to go.

You are clearly doing it wrong.

(For those that aren't aware of this rather old issue: have fun).

- ferdy

13 April, 2008

Permalink 12:44 UTC, by Fernando J. Pereda, 226 words, 209 views   English (US)
Categories: Gentoo

From yoswink: 1st Technological days of Isla Cristina

I'm proxy-posting this to Gentoo Planet from yoswink:

---

During the last week, the people of Isla Cristina (a beautiful town in the Atlantic coast with probably the best beaches of all Spain) organized an event called '1st Technological days of Isla Cristina'. They invited me to participate and give a talk about Gentoo.

On Friday I was there explaining what makes our distribution different, what the 'All about choice' is and the technology behind it. I shared the day with Spanish developers of other open source projects such as OpenBSD, NetBSD and KDE.

The day organization was perfect, any more to say, it couldn't be better. I want to thanks the people (teachers and students) from IES Mirabent, who fought to make this idea a reality in a small town of 22k people (is not so common to find this kind of event in Spain with official devs from big OSS projects even in the big cities or universities), and to the youth department of Isla Cristina for all they have done for me.

If someone want to take an example about how an event should treat a lecturer, please contact with them.

P.D: thanks to Julio Merio from NetBSD for lending me the computer (I forgot the damn Mini-DVI cable) and sorry to Antonio Larrosa from KDE, I ate some minutes of his time :(

---

15 January, 2008

Permalink 10:12 UTC, by Fernando J. Pereda, 87 words, 551 views   English (US)
Categories: Gentoo

On tool boxes

Apparently, people are bashing Joshua Jackson (a.k.a. tsunam) for posting his opinion (which happens to be shared among lots of us). So just in case someone hasn't read what he said yet, I'm going to link his posts here. Please, do read them:

http://tsunam.org/2008/01/12/in-response/
http://tsunam.org/2008/01/14/clarifications/
http://tsunam.org/2008/01/14/tool-box/

I simply can't trust Daniel Robbins after what he tried to do the last time he tried to come back. Has everybody forgotten that? I hope not.

No love.

- ferdy

28 November, 2007

Permalink 21:14 UTC, by Fernando J. Pereda, 718 words, 420 views   English (US)
Categories: Gentoo, Programming

Paludis meets Java, part III

Once we've converted native types we face the task of converting arbitrary classes and types. Another thing we'll need is extract the C++ type of a Java object (jobject in JNI).

For that task, we will follow the convention of calling the native pointers in Java classes _ptr. With that, we can define the following templates:

template <typename T_>
inline T_ * get_native_ptr(JNIEnv * env, const char * const class_name, jobject obj)
{
    jclass cls(env->FindClass(class_name));
    jfieldID ptr_field(env->GetFieldID(cls, "_ptr", "J"));
    jlong ptr(env->GetLongField(obj, ptr_field));
    env->DeleteLocalRef(cls);
    return from_java_ptr<T_>(ptr);
}

template <typename T_>
inline tr1::shared_ptr<T_> get_native_sptr(JNIEnv * env, const char * const class_name, jobject obj)
{
    jclass cls(env->FindClass(class_name));
    jfieldID ptr_field(env->GetFieldID(cls, "_ptr", "J"));
    jlong ptr(env->GetLongField(obj, ptr_field));
    env->DeleteLocalRef(cls);
    return from_java_ptr_sptr<T_>(ptr);
}

This should really be doing more error checking, but it is good enough for ilustrating how nice are things when using proper tools (both languages and libraries).

Converting arbitrary types also uses some template magic:

template <typename T_>
struct NativeToJavaTypeMapper
{
    jobject operator() (JNIEnv *, const T_ &);
};

Now we need specializations for each type we want to convert, for instance, converting a paludis' FSEntry into a java.io.File looks like the following:

template<>
struct NativeToJavaTypeMapper<FSEntry>
{
    jobject operator() (JNIEnv * env, const FSEntry & f)
    {
        jclass cls(env->FindClass("java/io/File"));
        jmethodID constructor(env->GetMethodID(cls, "<init>", "(Ljava/lang/String;)V"));
        jobject ret(env->NewObject(cls, constructor, to_java_string(env, stringify(f))));
        env->DeleteLocalRef(cls);
        return ret;
    }
};

Neat and clean.

For containers, a java.util.LinkedList would be used for paludis' Sequence; and java.util.TreeSet for paludis' Set:

template <typename T_, typename It_>
jobject range_to_list(JNIEnv * env, It_ begin, It_ end)
{
    jclass list_class(env->FindClass("java/util/LinkedList"));
    jmethodID constructor(env->GetMethodID(list_class, "<init>", "()V"));
    jobject our_list(env->NewObject(list_class, constructor));
    jmethodID add_method(env->GetMethodID(list_class, "add", "(Ljava/lang/Object;)Z"));

    for (It_ i(begin) ; i != end ; ++i)
        env->CallBooleanMethod(our_list, add_method, NativeToJavaTypeMapper<T_>()(env, *i));

    env->DeleteLocalRef(list_class);

    return our_list;
}

template <typename T_, typename It_>
jobject range_to_set(JNIEnv * env, It_ begin, It_ end)
{
    jclass set_class(env->FindClass("java/util/TreeSet"));
    jmethodID constructor(env->GetMethodID(set_class, "<init>", "()V"));
    jobject our_set(env->NewObject(set_class, constructor));
    jmethodID add_method(env->GetMethodID(set_class, "add", "(Ljava/lang/Object;)Z"));

    for (It_ i(begin) ; i != end ; ++i)
        env->CallBooleanMethod(our_set, add_method, NativeToJavaTypeMapper<T_>()(env, *i));

    env->DeleteLocalRef(set_class);

    return our_set;
}

And now defining NativeToJavaTypeMapper specializations for containers is quite easy:

template<>
template <typename T_>
struct NativeToJavaTypeMapper<tr1::shared_ptr<const Sequence<T_> > >
{
    jobject operator() (JNIEnv * env, const tr1::shared_ptr<const Sequence<T_> > & s)
    {
        return range_to_list<T_>(env, s->begin(), s->end());
    }
};

template<>
template <typename T_>
struct NativeToJavaTypeMapper<tr1::shared_ptr<const Set<T_> > >
{
    jobject operator() (JNIEnv * env, const tr1::shared_ptr<const Set<T_> > & s)
    {
        return range_to_set<T_>(env, s->begin(), s->end());
    }
};

I've spent a fair amount of the time fighting with make and the build system. It looks mostly sane now, though.

Dealing with exceptions has been a bit tricky, however, I think I have a good system to deal with it now, even though Ciaran tagged it as icky and ugly :). That'd be the topic of the next part of the series.

The documentation is currently at http://dev.gentoo.org/~ferdy/paludis-jni/ . All of that has been accomplished in:

[ $ ~/git/paludis/jni(jni) ] git diff --shortstat trunk..
 65 files changed, 4371 insertions(+), 0 deletions(-)

Which is not a lot of code for what's exposed.

— ferdy

19 November, 2007

Permalink 08:04 UTC, by Fernando J. Pereda, 488 words, 331 views   English (US)
Categories: Gentoo, Programming

Paludis meets Java, part II

After showing how is the structure of a regular Paludis class using JNI, next thing is showing part of the magic behind paludis_java.hh.

What's there is functions to convert Java types into Paludis (and C++ native) types and viceversa (this conversions exist only when needed, not for every single type). So, for instance, one of those conversions would be jboolean <--> bool and it looks like this:

inline jboolean to_java_boolean(bool b)
{
    return b ? JNI_TRUE : JNI_FALSE;
}

inline bool from_java_boolean(jboolean b)
{
    return b == JNI_TRUE;
}

That was easy, let me show you the dirty part. I call it dirty not because it is difficult or tricky to understand, but because it is a bit icky. It is the way we store the native Paludis pointers in Java classes:

inline jlong to_java_ptr(void * const ptr)
{
    return reinterpret_cast<jlong>(ptr);
}

template <typename T_>
inline T_ * from_java_ptr(jlong ptr)
{
    return reinterpret_cast<_ *>(ptr);
}

template <typename T_>
inline tr1::shared_ptr<T_> from_java_ptr_sptr(jlong ptr)
{
    return * reinterpret_cast<tr1::shared_ptr<T_> *>(ptr);
}

Although dirty, it is quite easy aswell. Something this bindings will be converting a lot is strings:

std::string
from_java_string(JNIEnv * const env, jstring s)
{
    const char * const c_s(env->GetStringUTFChars(s, 0));
    std::string result(c_s);
    env->ReleaseStringUTFChars(s, c_s);
    return result;
}

jstring
to_java_string(JNIEnv * const env, const std::string & s)
{
    return env->NewStringUTF(s.c_str());
}

And since C++ is such a nice language comparing and stringifying arbitrary types was just as easy (credits for this go to Mr. McCreesh):

template <typename T_>
jstring common_stringify(JNIEnv * const env, jlong ptr)
{
    return to_java_string(env, stringify(*from_java_ptr<T_>(ptr)));
}

template <typename T_>
jint common_compare(jlong lhs_ptr, jlong rhs_ptr)
{
    T_ * const lhs(from_java_ptr<T_>(lhs_ptr)), * const rhs(from_java_ptr<T_>(rhs_ptr));
    if (*lhs < *rhs)
        return -1;
    else if (*rhs < *lhs)
        return 1;
    else
        return 0;
}

This wasn't quite difficult and it certainly makes working with JNI easier. However, there is still stuff to do (actually, to show, since it is implemented and working in my git repository) like exception handling, converting arbitrary Paludis types and typesafe containers.

During the weekend I've written bindings for almost every core Paludis class and the patch is not that big:

[ $ ~/git/paludis(jni) ] git diff --shortstat trunk..
 30 files changed, 1975 insertions(+), 0 deletions(-)

Now it is time to stop the bindings for a while and start writing documentation, examples and integrating the bindings into the Paludis codebase properly.

Next part of the series will be about how I am converting arbitrary types and containers into Java types and typesafe collections respectively.

— ferdy

18 November, 2007

Permalink 11:28 UTC, by Fernando J. Pereda, 340 words, 405 views   English (US)
Categories: Gentoo, Programming

Paludis meets Java, part I

Some days ago, the Wearer of the shiny hat started tinkering with JNI bindings for Paludis.

Even if we all think Java is perverse and should be avoided at all costs. Having used Java for the last four years and having studied part of the Java5 code I thought I could use everything I learnt and took the task of developing and maintaining the JNI bindings.

It has all been relatively easy. It's good that Ciaran started them; because his experience with the Ruby bindings gave the key to developing the Java bindings cleanly.

What we are currently doing is storing a C++ pointer in Java classes and passing it around in native methods. Then we delete it when Java's garbage collector decides it is good to call finalize.

So it mostly looks like this:

package paludis;
import paludis.Paludis;

public class Foo {
    private static Paludis _load_the_frickin_paludis_library = new Paludis();
    private long _ptr;

    private static native long _construct_string(String s);
    private static native void _destruct(long ptr);

    private static native boolean _is_foo(long ptr);

    protected void finalize() throws Throwable {
        _destruct(_ptr);
        super.finalize();
    }

    public Foo(String s) {
        _ptr = _construct_string(s);
    }

    public boolean isFoo() {
        return _is_foo(_ptr);
    }
}

Then the C++ part looks like this:

/* vim: set sw=4 sts=4 et foldmethod=syntax : */

#include "foo.hh"
#include "paludis_java.hh"
#include <jni.h>
#include <paludis/foo.hh>

using namespace paludis;
using namespace paludis::java;

JNIEXPORT jlong JNICALL
Java_paludis_Foo__1construct_1string(JNIEnv * env, jclass, jstring s)
{
    return to_java_ptr(new Foo(from_java_string(env, s)));
}

JNIEXPORT void JNICALL
Java_paludis_Foo__1destruct(JNIEnv *, jclass, jlong ptr)
{
    delete from_java_ptr<Foo>(ptr);
}

JNIEXPORT jboolean JNICALL
Java_paludis_Foo__1is_1foo(JNIEnv *, jclass, jlong ptr)
{
    return to_java_boolean(from_java_ptr<Foo>(ptr)->is_foo());
}

Here, all the magic is happening behind the scenes in the paludis_java.hh header which I'll show in a future post of the Paludis meets Java series.

— ferdy

9 November, 2007

Permalink 22:48 UTC, by Fernando J. Pereda, 124 words, 484 views   English (US)
Categories: Gentoo, Rants

I wonder who is acting like a moron...

It is often surprising how some people can really lose control of a situation.

Take this example http://dev.gentoo.org/~ferdy/tmp/seemant-moron.log . It is actually sad having to deal with that kind of thing. I asked three times for an apology and (surprise surprise) I didn't get one. One publicly in IRC, another one in a /query and a third one by mail.

Besides wondering who is the one acting like a moron, I really wonder why people have the feeling that Gentoo is oh so nice and friendly.

No love.

— ferdy

PS: Despite of his attitude, I still can't be bothered with personal issues. So if he wanted me to have an issue with him, I'm thankful he failed.

7 November, 2007

Permalink 20:14 UTC, by Fernando J. Pereda, 253 words, 187 views   English (US)
Categories: Personal

Been to Morocco, loved it

I didn't really want to go there because it meant lots of car (4100 Km in a week) and not enough time to enjoy and getting to know each place we went.

ferdy as a twareg

In the end, well, I went. And I'm quite happy I did it. It is a very interesting country where the first thing you learn is:

Hurry kills...
    and lazyness re-kills. — Anyone in Morocco

We crossed the Atlas twice. Some of the views up there are just amazing.

We also went to the dunes in Merzouga. If you ever consider going to Morocco, you can't miss a couple of nights in 'Atlas du Sable' with Ali's crew, those guys make it very comfortable and enjoyable.

We also visited M'Hamid and that part of Morocco, that part was a bit harder emotionally. But it is still enlightening and a very interesting place to visit.

Last place was Marrakech. I loved it so much that I'll have to go again because two nights is not enough for this city.

Only complains are: Too many hours of 'car stuck because of sand' and not enough time to get to know any place. but all in all it's been a wonderful trip and a very nice experience. Their way of living and thinking is just too different from anything in Europe.

We took hundreds of photos, some of them are on my picasaweb album: http://picasaweb.google.com/fpereda/MoroccoTour07 .

If you ever have the oportunity to go to Morocco, go for it.

— ferdy

11 June, 2007

Permalink 19:39 UTC, by Fernando J. Pereda, 211 words, 2738 views   English (US)
Categories: Uncategorized, Programming

Hidden PI

The people from Gaussianos.com (spanish blog abouth math) posted a couple of algorithms to calculate Pi and asked readers to provide some more.

I recently read on The Computational Beauty of Nature that Pi is hidden in the Mandelbrot set:

Take the mandelbrot iteration function:

z0 = 0
z = z^2 + c

And the initial complex number:

c = -3/4 + a * i

That set of complex numbers lays just between the two main parts of the body of the set, it is also known as the 'neck' (since it joins the cardiod with the biggest 'head').

For a = 0 the point belongs to the mandelbrot set. Let k be the number of iterations needed for a point (c = -3/4 + a * i) to reach modulus greater than 2 (escape radius), as a approaches to zero, k * a approaches to pi.

I wrote a simple C program that shows this (http://dev.gentoo.org/~ferdy/stuff/pi_mandel_gmp.c). When compiled, linked against libgmp and run, it outputs something like the following:

  a      || k         || aprox. pi
 --------++-----------++-----------
  1      || 3         || 3.0000000
  0.1    || 33        || 3.3000000
  0.01   || 315       || 3.1500000
  0.001  || 3143      || 3.1430000
  0.0001 || 31417     || 3.1417000
  1e-05  || 314160    || 3.1416000
  1e-06  || 3141593   || 3.1415930
  1e-07  || 31415927  || 3.1415927

It is an utterly expensive and pointless way to calculate pi, but it is one of the most obscure and weird ways to do it :)

Of course, all the credit goes to Dave Boll, who discovered the fact on 1991.

- ferdy

17 May , 2006

Permalink 13:46 UTC, by Fernando J. Pereda, 392 words, 3324 views   English (US)
Categories: Uncategorized

Random Git Stuff

Switching between projects using different SCMs is painful sometimes, and I always fail to remember the branch I'm on in my Git repositories. I use some bashrc/PS1 magic to show some SCM information in my PS1, I thought someone would find it useful: bashrc-scm.

Lately I've been working on RepoDoc whenever I've found a bit of free time. We are using Git as our SCM mainly because it is easy and very flexible and we can follow a pseudo-centralized workflow that probably only suits us :) We faced some problems with it but given the flexibility of Git, fixing them was really easy.

We keep a central repository with one branch per committer plus master. Those are the top-level branches, and not everybody can update every brach, so the traditional Unix filesystem permissions doesn't solve our problem. Then we can create as many temporal branches as we want under the tmp/ directory.

Also, we decided to keep a 'fast-forward only' policy on top-level branches, so everything has to be cooked in temporal branches first and then cleanly merged into top-level branches.

To enforce both policies (permissions and 'fast-forward only') we call a script from the update hook who does all the magic: http://dev.gentoo.org/~ferdy/stuff/enforce-perms. The users-allowed file is something like:

refs/heads/master$  alice bob
refs/heads/alice$   alice
refs/heads/bob$     bob
refs/heads/eve$     eve
refs/heads/tmp/     ^
refs/tags/          alice

Today I also decided to hack a CIA bot to send repodoc stats. It was fairly easy since the ciabot.pl included in Cogito did almost everything I wanted. However, being a perl-ignorant I rewrote the whole thing in bash to suit my needs, grab it from http://dev.gentoo.org/~ferdy/stuff/ciabot.bash.

For those with the ability to read or understand some Spanish I wrote a little introduction to Git: http://dev.gentoo.org/~ferdy/git-intro/

I have also been trying to import the gentoo-x86 module into Git without much luck, both parsecvs and git-cvsimport failed, I'll probably try Tailor later. I haven't payed much attention to it anyway, since I'm a bit busy with university stuff. I guess I should seek help in the Git mailing list once I take it seriously.

Oh, and by the way, there is a new Git version in the tree. Go grab it!

- ferdy

19 January, 2006

Permalink 09:18 UTC, by Fernando J. Pereda, 113 words, 7446 views   English (US)
Categories: Gentoo

Mutt macro trick

So Greg KH wonders how to fix his macro in mutt.

Here you have something that works. Doesn't do anything fancy (in fact it is useless), but I guess you could adapt it to suit your needs:

macro index T "<enter-command>unset wait_key\n \
                <pipe-message>cat - > /home/ferdy/foo.blah\n \
                <shell-escape>vim -c 'set ft=mail' /home/ferdy/foo.blah\n \
                <enter-command>set wait_key\n"

I tried using 'decode-save' and/or 'save-message' but for some reason it didn't work. I guess you could replace 'x.sh' or almost all of it with a mutt macro like the one above.

Cheers,
Ferdy

10 January, 2006

Permalink 17:21 UTC, by Fernando J. Pereda, 317 words, 6495 views   English (US)
Categories: Gentoo

Solving the Missionaries and Cannibals puzzle

There is a traditional puzzle where 3 missionaries and 3 cannibals have to cross a river using a small canoe. Rules are:

* You cannot have more cannibals than missionaries in either bank because cannibals will eat missionaries.
* The canoe can be run by either one or two persons. Both cannibals and missionaries know how to run it.

This puzzle is really easy to solve either by hand or programming. However, hacking a script to solve it is always more challenging than solving it by hand. Juanjo proposes a solution using Ruby in Misioneros y caníbales (in Spanish). I thought I could try solving it in Haskell.

It's been really easy to solve it in Haskell given the nature of the language. The proposed solution is a specific application of a computation over graphs:

The goal is finding every possible route between two nodes of a network graph, and then choose the shortest one. Once you define the possible succesors of a given state problem, finding routes between two states is straightforward. One particular oddity of this problem is the fact that the network graph has loops, so the algorithm has to check for them.

The recursion step (with implicit backtracking) is not difficult at all. It will take an initial state as first argument, and a list of visited states as a second argument. Returns a list of solutions, each solution represented by a list of states (nodes in the graph).

solveStep :: ProbSt -> [ProbSt] -> [[ProbSt]]
solveStep prob probs = if problemSolved prob
                       then [prob:probs]
                       else concat [ solveStep p' (prob:probs) | p' <- nextStates prob
                                                               , p' `notElem` probs ]

Where nextStates gives a list of succesors for a given problem, and problemSolved checks if we solved the problem. Now the function to really solve the problem can be defined easily in terms of solveStep:

solveProblem :: [[ProbSt]]
solveProblem = solveStep ((3,3),(0,0),Start) []

Ok, stop talking, here is the code: MisCan.hs.

Cheers,
Ferdy

5 December, 2005

Permalink 10:07 UTC, by Fernando J. Pereda, 616 words, 576 views   English (US)
Categories: Gentoo

Status update (alpha,haskell,ctags,...)

So It's been a long time since I wrote anything, not because I've done much for Gentoo but because Uni starts sucking once again.

However I found some time to do a couple of (maybe) interesting things:

I added some base-system binary packages for alpha. So if you screwed your alpha instalation doing something brave (or stupid) just take a look at http://dev.gentoo.org/~ferdy/bins/alpha/. You should be able to recover your system if you have a working busybox (which you SHOULD have).

I also managed to build 'The Glorious Glasgow Haskell Compiler' under alpha. Even if it is an unregisterised build, the result binaries are pretty usable (although they are HUGE). I built darcs with it and works perfectly. If you want to give it a try, get it from the url above, and put it in /usr/portage/packages/. You should be able to 'emerge -k' it by just removing the <virtual/ghc-6.5 dependency in dev-lang/ghc-6.4.1-r1.

I'll work with the gentoo-haskell guys to get it into the portage tree soon. Since I'm learning haskell, expect more haskell-related alpha porting :)

I also hacked a portage atom parser in haskell for a script I've been meaning to do for a long time. Doesn't do anything fancy yet since I'm still implementing the Ord class operators. However it is considerably fast, it parses ~71000 lines in less than 1.5 seconds. Get AtomParser.hs and see a proof of concept showing its use in parser-test.hs. ( I'm still learning haskell so yes, it is really easy to improve my code ).

Since ctags is almost unmaintained upstream I've been collecting some useful patches around the net and might consider give it a big bump in the near future. The patches series are (in order):

  • Haskell support [by me]
  • Very basic ObjC support (ObjC hackers are welcome to send me ideas and code to improve the regexes) [by me]
  • Add patch to make Ruby class names in the form Foo::Bar work [by Ciaran McCreesh]
  • Add patch to improve C handling [by vim hackers, pointed out by Ciaran McCreesh]
  • Add support for Java 5 generics [found somewhere in the ctags forums]
  • Ebuild syntax support [by Ciaran McCreesh]

If you have an interesting and useful patch for ctags, please send it my way so I can integrate it in the next bump if I ever manage to do it. I'm maintaining all those patches in a stgit repository that I might share if anybody asks me to do it.

Also the Alpha Arch Testers project is reaching its final stage. We've got a quiz and we are giving the final touches to a policy document describing how we should behave (i.e. herd and arch-testers) one to each other.

Also I'm looking forward to Stephen Bennett's SELinux work under alpha. He kind of promised to test the hardened-sources; it'll rock if he gets them work; because since the grsec-sources were removed we've got no 'secure' sources in the tree.

And last (and probably least) I wrote a dirty bash script some time ago and thought I might share. It simply lists the files that are no longer 'claimed' by any package installed under /usr/portage/distfiles. I know there are some nice python scripts around but I found this one to be way faster than those. WARNING: It is a hack, it won't work without gnu-sed and will probably miss some files. However, it seems to work great here. If you want to give it a try, it is here (distfiles-clean). ( More scripts in http://gentoo-es.org/~ferdy/git/?p=gentoo-scripts.git;a=summary )

Ok time to get back to the mips assembly University work...

Cheers,
Ferdy

5 October, 2005

Permalink 16:48 UTC, by Fernando J. Pereda, 189 words, 484 views   English (US)
Categories: Gentoo

Multiple git enhancements

I've been working on dev-util/git and git-related software for a week and today I committed the following git related packages and enhancements:

dev-util/git - An init script to use git-daemon. It is way faster than HTTP for 'clone' and 'fetch' (and thus 'pull'). A really nice way to share repositories if you don't have lots of bandwidth.

dev-util/stgit - Stacked GIT is a SCM on top of GIT that works a la quilt. Lets you manage a series of patches in a stack fashion.

www-apps/gitweb - Gitweb is a handy cgi script to show git repositories 'via Web'. It uses webapp.eclass. I've added this one to package.mask because I think it needs a bit more testing before going to ~arch. Unmask it, test it, and send feedback please :)

I started using git a month ago and I've migrated almost all my code to git. The documentation is good enough and git's layout is in fact very easy. Moreover, there are scripts to import both cvs and arch repositories (git-cvsimport and git-archimport). Both of them work pretty good as far as I know.

Test and enjoy them ;-)

20 September, 2005

Permalink 10:56 UTC, by Fernando J. Pereda, 94 words, 1846 views   English (US)
Categories: Gentoo

New mutt and maildrop versions

Yesterday I added a new mutt version to the tree (1.5.11, ~arch). Except from a bug regarding SASL that I fixed a couple of hours after adding it; should work fine.

I also added maildrop-2.0.0 to the tree AND package.mask. This version comes with nice features such as fam integration and uses libpcre for pattern matching. Please test it and send bugs if you find any. I'm using it without problems so it shouldn't break too badly :)

A simple:

# echo '>=mail-filter/maildrop-2.0.0' >> /etc/portage/package.unmask
# emerge -va maildrop

should do it.

Cheers,
Ferdy

28 August, 2005

Permalink 13:08 UTC, by Fernando J. Pereda, 167 words, 432 views   English (US)
Categories: Rants

Groups forgetting basic rules

Somehow big groups tend to forget basic rules, (i.e. someone from the group breaks the rule), even if the rule is one of the Top5 rules they have to follow. One common example of this is the (BTW, really easy) Keywording Policy in Gentoo. Luckily our Sparc team is very good at fighting people forgetting it :)

But today I'm not going to remind the Keywording Policy since surprisingly enough nobody broke it recently. I want to remind every person participating in mailing lists, usenet groups, ... to read again the Netiquette. This specially applies to my LUG fellows, it's mailling-list moderator/administrator and of course myself.

As somebody said the quality of our LUG and therefore its mailling-list only depends on our behavior. Also please consider reading Email Etiquette and the comments on top-posting. The constant breaking of this basic rules will keep valuable people out of the list and you will even force some of them to leave the LUG and cease their activity.

Cheers,
Ferdy

5 August, 2005

Permalink 16:41 UTC, by Fernando J. Pereda, 138 words, 457 views   English (US)
Categories: Uncategorized

PAY, it depends on how do you understand licenses

Hey PAY!

The answer to your question about free licenses depends on how you understand a license. What do you want to do ? protect the work or give rights to your users ?

If you see the license as a way to protect the code itself (the music in this particular case); then there is no way the BY-SA is 'more free' than the BY-NC-SA.

However, some people (me among them) think licenses are meant to give rights to users. With this idea, the BY-SA is far 'more free' than the BY-NC-SA; because the former allows derivatives works not allowed by the latter. Following with this argument you come to the conclusion that the BY is the 'most free' among the CreativeCommons licenses.

Of course thats only my opinion and since IANAL I might be totally off.

Cheers,
Ferdy

4 August, 2005

Permalink 07:04 UTC, by Fernando J. Pereda, 16 words, 395 views   English (US)
Categories: Uncategorized

... then switch to PostgreSQL

David::, if you can't use MySQL; then try to switch to PostgreSQL. BTW, enjoy with it :)

:: Next Page >>

Fernando J. Pereda

Here you will find stories about Gentoo net-mail development from Fernando J. Pereda (ferdy).

| Next >

May 2008
Mon Tue Wed Thu Fri Sat Sun
<< <     
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  

Search

Categories

Misc

XML Feeds

What is RSS?

Who's Online?

  • Guest Users: 86

powered by
b2evolution