My hobbyist coding updates and releases as the mysterious "Mr. Tines"

Friday 24 July 2009

The lock-free queue revisited

The previous entry gave the queue itself, and didn't worry about locks that might or might not be taken out by the ancillary code. To avoid allocations and deallocations of queue nodes in the steady state, get rid of the STL list and keep them on a stack --

/*
            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2004 Sam Hocevar
  14 rue de Plaisance, 75014 Paris, France
 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO. */

/* This program is free software. It comes without any warranty, to
 * the extent permitted by applicable law. You can redistribute it
 * and/or modify it under the terms of the Do What The Fuck You Want
 * To Public License, Version 2, as published by Sam Hocevar. See
 * http://sam.zoy.org/wtfpl/COPYING for more details. */ 

#pragma once

// suppress 64-bit ready warning about casting on the win32 platform (only)
#pragma warning(disable:4311)
#pragma warning(disable:4312)

// After Sutter in Dr. Dobbs -- http://ddj.com/cpp/210604448?pgno=2
#include <list>
#include "Windows.h"

template <typename T>
class SimpleQueue {
public:
    typedef T* Tptr;                                // should really be a smart_pointer<T>
    typedef const T * Tcptr;

private:
    SimpleQueue(const SimpleQueue &);               // Not copyable
     SimpleQueue & operator= (const SimpleQueue &); // Not assignable

  struct Node {
     Node( Tptr val ) : value(val), next(NULL) { }
    Node() : next(NULL) { value = NULL; }
    Tptr value;
    Node* next;
  };

  Node * freeStack;             // for producer only
  Node* first;                  // for producer only
  Node *divider, *last;         // shared -- Use explicit atomic compares only

  // Allocator/Deallocator for nodes -- 
  // only used in the producer thread
  // OR in the destructor.
  Node * Get(Tptr val)
  {
     if(freeStack)
     {
        // Clean because of Release
        Node * next = freeStack;
        freeStack = next->next;
        next->value = val;
        return next;
     }

     // clean by construction
     return new Node(val);     
  }

  // Avoids costly free() while running
  void Release(Node * node)
  {
        // reset the node to clean before shelving it
        node->value = NULL;
        node->next = freeStack;
        freeStack = node;
  }


public:
    SimpleQueue() : freeStack(NULL) {
    first = divider = last = Get(NULL);                         // add dummy separator
  }

  ~SimpleQueue() {
    while( first != NULL ) {               // release the list
      Node* tmp = first;
      first = tmp->next;
      delete tmp;
    }

     // Require -- Producer thread calls this or is dead
     while(freeStack)
     {
          delete Get(NULL);
     }
  }

  // Produce is called on the producer thread only:
  void Produce( Tptr t ) {
    last->next = Get(t);                            // add the new item
    InterlockedExchangePointer(&last, last->next);  // publish it : atomic last = last->next;


    // Burn the consumed part of the queue
    for( PVOID looper = first;                     // non-null; pointer read is atomic; atomic while( first != divider )
           InterlockedCompareExchangePointer(&looper, NULL, divider), looper;
           looper = first)
     {
      Node* tmp = first;
      first = first->next;

      Release(tmp);
    }
  }

  // Consume is called on the consumer thread only:
  bool Consume( Tptr & result ) {

     PVOID choice = divider;                                  // non-null; pointer read is atomic
     InterlockedCompareExchangePointer(&choice, NULL, last);

     if(choice)
     {
        if(!divider || ! divider->next || ! divider->next->value) 
            printf("help!");

        result = divider->next->value;                        // C: copy it back
        choice = divider;
        InterlockedExchangePointer(&divider, divider->next);  // D: publish that we took it : atomic divider = divider->next;
        reinterpret_cast<Node*>(choice)->next = NULL;
        return true;                                          // and report success
    }

    return false;                                             // else report empty
  }
};

#pragma warning(default:4312)
#pragma warning(default:4311)

Next add a recycling class to avoid having to keep allocating and reallocating payload objects. C++ sucks as a functional language (without all the heavyweight Boost machinery), so import the functions we need via static polymorphic constraints on templated types.

/*
            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2004 Sam Hocevar
  14 rue de Plaisance, 75014 Paris, France
 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO. */

/* This program is free software. It comes without any warranty, to
 * the extent permitted by applicable law. You can redistribute it
 * and/or modify it under the terms of the Do What The Fuck You Want
 * To Public License, Version 2, as published by Sam Hocevar. See
 * http://sam.zoy.org/wtfpl/COPYING for more details. */ 
#pragma once

#include "SimpleQueue.h"

template <typename T, typename TSource, typename TReceiver>
class ConveyorBelt {
    SimpleQueue<T> forward;
    SimpleQueue<T> reverse;

public:
    

    ConveyorBelt() {}
    ~ConveyorBelt() 
    {
        SimpleQueue<T>::Tptr t;
        while(forward.Consume(t))
        {
            delete t;
        }
        while(reverse.Consume(t))
        {
            delete t;
        }
    }

    void Accept(TSource & source)
    {
        SimpleQueue<T>::Tptr t;
        if(!reverse.Consume(t))
        {
            t = new T();
        }
        source.Set(t);
        forward.Produce(t);
    }

    bool Display(TReceiver & sink)
    {
        SimpleQueue<T>::Tptr t;
        if(!forward.Consume(t))
            return false;

        SimpleQueue<T>::Tcptr tconst = t;
        sink.Use(tconst);
        t->Reset();


        reverse.Produce(t);
        return true;
    }
};

All T records are owned by the ConveyorBelt, and we just loan them out to the TSource and TReceiver objects to write into or read from. Once read, they are recycled back to the producing thread.

A test harness looks like this --

/*
            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2004 Sam Hocevar
  14 rue de Plaisance, 75014 Paris, France
 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO. */

/* This program is free software. It comes without any warranty, to
 * the extent permitted by applicable law. You can redistribute it
 * and/or modify it under the terms of the Do What The Fuck You Want
 * To Public License, Version 2, as published by Sam Hocevar. See
 * http://sam.zoy.org/wtfpl/COPYING for more details. */ 

#include "stdafx.h"
#include "SimpleQueue.h"
#include "ConveyorBelt.h"

using namespace System;
using namespace System::Threading;


class MarkedBuffer {
public:
    size_t start;
    size_t end;
    char data[16384];

    MarkedBuffer() : start(0), end(0) 
    { Reset(); }

    void Reset()
    { memset(data, 0, sizeof(data)); }
};

class Endpoints {
public:
    size_t source;
    size_t sink;

    Endpoints() : source(0), sink(0) {}
    void Set(MarkedBuffer * t)
    {
        t->start = source;
    }
    void Use(MarkedBuffer const * t)
    {
        sink = t->start;
    }
};


ref class Work
{
public:

   static ConveyorBelt<MarkedBuffer, Endpoints, Endpoints> * q2;
   static Endpoints * e;

   static void Produce2()
   {
      Console::WriteLine( "Producer thread procedure." );
       for(int i=0; i<32768; ++i)
       {
            e->source = i;
            q2->Accept(*e);
            if(0 == (i%100)) Thread::Sleep(200);
            else Thread::Sleep(0);
       }
      Console::WriteLine( "Producer thread finishhd." );
   }

   static void Consume2()
   {
      Console::WriteLine( "Consumer thread procedure." );
       int latest = -1;
       while(latest < 32767)
       {
           if(q2->Display(*e))
            {
                 if(e->sink != size_t(latest+1))
                 {
      Console::WriteLine( "Consumer thread procedure -- failure." );
                 }
                 latest = int(e->sink);
            }
       }
      Console::WriteLine( "Consumer thread finished." );
   }
};


int main(array<System::String ^> ^)
{

     {
          ConveyorBelt<MarkedBuffer, Endpoints, Endpoints> queue;
          Endpoints e;

          Work::q2 = &queue;
          Work::e = &e;

          ThreadStart ^ producerDelegate = gcnew ThreadStart( &Work::Produce2 );
          Thread ^ producerThread = gcnew Thread( producerDelegate );
          ThreadStart ^ consumerDelegate = gcnew ThreadStart( &Work::Consume2 );
          Thread ^ consumerThread = gcnew Thread( consumerDelegate );


          producerThread->Start();
          consumerThread->Start();

          producerThread->Join();
          consumerThread->Join();
     }

      Console::WriteLine( "Completed." );

    return 0;
}

Where the MarkedBuffer type is representative of the uses I have made of such a queue inside a proxying application -- a packet read from the network into the data array or composed for writing to the network, with start and end offsets as marked; the data being conveyed between threads service client facing and server facing sockets.

Using the ConveyorBelt to carry data, allocations will take place until a steady state is reached, and may infrequently happen as spikes load the queue; all deallocations are deferred to the destruction of the system.

Wednesday 22 July 2009

A simple LockFree Queue (C++, Windows)

Prompted by some discussion on StackOverflow today...

This is the simple single-producer, single-consumer version of the Lock-Free Queue as published by Herb Sutter in DDJ, but adapted to replace the C++0x style atomic<Node*> with Win32 API calls to InterlockedExchangePointer and InterlockedCompareExchangePointer. Converting the multiple producers/consumers case is left as a trivial exercise for the reader.

So is doing the free-list manually, as a stack of Nodes rather than bringing in a gratuitous std::list.

/*
            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2004 Sam Hocevar
  14 rue de Plaisance, 75014 Paris, France
 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO. */

/* This program is free software. It comes without any warranty, to
 * the extent permitted by applicable law. You can redistribute it
 * and/or modify it under the terms of the Do What The Fuck You Want
 * To Public License, Version 2, as published by Sam Hocevar. See
 * http://sam.zoy.org/wtfpl/COPYING for more details. */ 

#pragma once

// suppress 64-bit ready warning about casting on the win32 platform (only)
#pragma warning(disable:4311)
#pragma warning(disable:4312)

// After Sutter in Dr. Dobbs -- http://ddj.com/cpp/210604448?pgno=2
#include <list>
#include "Windows.h"

template <typename T>
class SimpleQueue {

    typedef T* Tptr;                                // should really be a smart_pointer<T>

private:
    SimpleQueue(const SimpleQueue &);               // Not copyable
     SimpleQueue & operator= (const SimpleQueue &); // Not assignable

  struct Node {
     Node( Tptr val ) : value(val), next(NULL) { }
    Node() : next(NULL) { value = NULL; }
    Tptr value;
    Node* next;
  };

  std::list<Node *> freeList;   // for producer only
  Node* first;                  // for producer only
  Node *divider, *last;         // shared -- Use explicit atomic compares only

  // Allocator/Deallocator for nodes -- 
  // only used in the producer thread
  // OR in the destructor.
  Node * Get(Tptr val)
  {
     if(!freeList.empty())
     {
        // Clean because of Release
        Node * next = freeList.front();
        freeList.pop_front();
        next->value = val;
        return next;
     }

     // clean by construction
     return new Node(val);     
  }

  // Avoids costly free() while running
  void Release(Node * node)
  {
        // reset the node to clean before shelving it
        node->value = NULL;
        node->next = NULL;
        freeList.push_back(node);
  }


public:
  SimpleQueue() {
    first = divider = last = Get(NULL);                         // add dummy separator
  }

  ~SimpleQueue() {
    while( first != NULL ) {               // release the list
      Node* tmp = first;
      first = tmp->next;
      delete tmp;
    }

     // Require -- Producer thread calls this or is dead
     while(!freeList.empty())
     {
          delete Get(NULL);
     }
  }

  // Produce is called on the producer thread only:
  void Produce( Tptr t ) {
    last->next = Get(t);                            // add the new item
    InterlockedExchangePointer(&last, last->next);  // publish it

    // Burn the consumed part of the queue
    for( PVOID looper = first;                     // non-null; pointer read is atomic
           InterlockedCompareExchangePointer(&looper, NULL, divider), looper;
           looper = first)
     {
      Node* tmp = first;
      first = first->next;
      Release(tmp);
    }
  }

  // Consume is called on the consumer thread only:
  bool Consume( Tptr & result ) {

     PVOID choice = divider;                                  // non-null; pointer read is atomic
     InterlockedCompareExchangePointer(&choice, NULL, last);

     if(choice)
     {
        result = divider->next->value;                        // C: copy it back
        choice = divider;

        InterlockedExchangePointer(&divider, divider->next);  // D: publish that we took it
        reinterpret_cast<Node*>(choice)->next = NULL;
        return true;                                          // and report success
    }

    return false;                                             // else report empty
  }
};

#pragma warning(default:4312)
#pragma warning(default:4311)

And a simple test harness using C++/CLI to make the threading simpler to write

/*
            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
                    Version 2, December 2004

 Copyright (C) 2004 Sam Hocevar
  14 rue de Plaisance, 75014 Paris, France
 Everyone is permitted to copy and distribute verbatim or modified
 copies of this license document, and changing it is allowed as long
 as the name is changed.

            DO WHAT THE FUCK YOU WANT TO PUBLIC LICENSE
   TERMS AND CONDITIONS FOR COPYING, DISTRIBUTION AND MODIFICATION

  0. You just DO WHAT THE FUCK YOU WANT TO. */

/* This program is free software. It comes without any warranty, to
 * the extent permitted by applicable law. You can redistribute it
 * and/or modify it under the terms of the Do What The Fuck You Want
 * To Public License, Version 2, as published by Sam Hocevar. See
 * http://sam.zoy.org/wtfpl/COPYING for more details. */ 

#include "stdafx.h"
#include "SimpleQueue.h"

using namespace System;
using namespace System::Threading;
ref class Work
{
public:
   static void Produce()
   {
      Console::WriteLine( "Producer thread procedure." );
       for(int i=0; i<32768; ++i)
       {
            int * data = reinterpret_cast<int*>(malloc(sizeof(int)));
            *data = i;
            q->Produce(data);
            if(0 == (i%1000)) Thread::Sleep(20);
       }
      Console::WriteLine( "Producer thread finished." );
   }

   static void Consume()
   {
      Console::WriteLine( "Consumer thread procedure." );
       int latest = -1;
       while(latest < 32767)
       {
            int * data;
            if(q->Consume(data))
            {
                 if(data[0] != latest+1)
                 {
      Console::WriteLine( "Consumer thread procedure -- failure." );
                 }
                 latest = data[0];
                 free(data);
            }
       }
      Console::WriteLine( "Consumer thread finished." );
   }

   static SimpleQueue<int> * q;

};


int main(array<System::String ^> ^)
{
     {
          SimpleQueue<int> queue;
          Work::q = &queue;

          ThreadStart ^ producerDelegate = gcnew ThreadStart( &Work::Produce );
          Thread ^ producerThread = gcnew Thread( producerDelegate );
          ThreadStart ^ consumerDelegate = gcnew ThreadStart( &Work::Consume );
          Thread ^ consumerThread = gcnew Thread( consumerDelegate );


          producerThread->Start();
          consumerThread->Start();
          producerThread->Join();
          consumerThread->Join();
     }

      Console::WriteLine( "Completed." );

    return 0;
}

Tuesday 26 May 2009

The Jython/Scala stack revisited

After last year's experiments, another refinement in the process of getting the two languages to talk, this time from inside NetBeans.

Last year, doing everything from the command line, I got across the language bridge by adding the scala jar to the classpath. Inside NetBeans, you get a little way along the road by adding the scala-library jar and the jars from the scala layer of the stack to the project Python Path. This will let you import types, and see that traits have the expected members. Classes, however, appear as None valued.

For development purposes, you can, instead of adding the jars to the classpath, add them to sys.path instead, like:

sys.path.append(r'C:\Users\Tines\.netbeans\6.5\scala\scala-2.7.3.final\lib\scala-library.jar')
sys.path.append(r'C:\Users\Tines\Documents\FTPStack\FTPlib\dist\FTPLib.jar')

For a real app, rather than hard-coding, these file paths could be supplied as arguments.

Scala companion objects, with names ending in $ don't show up at all in the namespaces when imported into Jython, so anything static-like will have to be accessed through a throwaway class instance.

Monday 11 May 2009

Scala is not C#

Took a while to debug what was going wrong here

        val tmp = toUnsigned(leftSide.digits(i)) * toUnsigned(rightSide.digits(j)))
           +  toUnsigned(da(k)) + carry

because it compiles, silently discarding the fact that this is two statements, the second with no immediately apparent side-effects.

It should be more like

        val tmp = (
          (toUnsigned(leftSide.digits(i)) * toUnsigned(rightSide.digits(j))) +
          toUnsigned(da(k)) + carry)

where the parentheses and the trailing operators give a belt-and-braces approach to delineating the statement boundaries.

Saturday 9 May 2009

Integrating Scala with Erlang -- Initial steps

So, I've started a parallel implementation of jinterface 1.5 in Scala, the idea being

  1. To teach myself Scala by doing
  2. To experiment with the actor-based concurrency as a counterparty to the Erlang model
  3. To experiment with Scala as a dual VM technology

So far, just the term-representation classes, and the start of the Input/Decode and Output/Encode part; and some unit tests, only for Atom so far.

I am impressed at how much I've been able to do without bringing in platform types that I will need to abstract out. What was memory-based I/O in Java or C# becomes Seq[Byte] or Queue[Byte] as appropriate and basing all exceptions off the shared name Exception root class gets rid of any dependence on concrete subclasses. It's only BigInt that is a known problem so far, where I'll need to factor out a platform abstraction later. Of course abstracting ZLib support is a task lurking in the near future, as well.

The first noticeable difference from trying to tidy the C#2 port of an older Java version is that the functional style and rich library support make a lot of previously long-winded support methods significantly more expressive. Contrast the Erlang list (of integer values) to String

public System.String StringValue
        {
            get
            {
                char[] body = new char[Arity];
                ReadOnlyCollection<IObject> e = Elements;
                for (int i = 0; i < Arity; ++i)
                {
                    Integer v = e[i] as Integer;
                    if (null == v) body[i] = '?';
                    else
                    {
                        System.Diagnostics.Debug.Assert(v != null && v.Value != null);
                        char? c = v.Value.ToChar();
                        if (null == c) c = '?';
                        body[i] = (char)c;
                    }
                }
                return new string(body);
            }
        }
// and elsewhere
        public char? ToChar()
        {
            try
            {
                return (char)System.UInt16.Parse(this.ToString(), System.Globalization.NumberStyles.Integer, System.Globalization.CultureInfo.InvariantCulture);
            }
            catch (OverflowException)
            {
                return null;
            }
        }

with

def AsString =
  {
    (Elements map List.AsChar).mkString
  }
// and elsewhere
  def AsChar(obj : IObject) =
    obj match
    {
      case c : Integer if c.Value < (Integer.Zero + Char.MinValue.toInt) => '?'
      case c : Integer if c.Value >= (Integer.Zero + Char.MaxValue.toInt) => '?'
      case c : Integer => c.Value.intValue.toChar
      case _ => '?'
    }

Yes, using C#3's functional extensions, that too could be simplified; this is really the Java equivalent of doing that.

Code drop on the MediaFire page.

Monday 27 April 2009

ZLIB and .Net

A recurring problem in several of the projects I have in the pipeline is the matter of handling ZLIB. Java, through java.util.zip offers ZLIB compression with a 32k byte window (but no means of tuning the window) with the DeflaterOutputStream. The .Net framework doesn't offer direct ZLIB at all, but provides naked Deflate via System.IO.Compression.DeflateStream.

That gives us enough to be able to reflate the output of a ZLIB deflation, since a ZLIB is a 2 byte header, a deflate section and finally a 4 byte checksum:

import clr    
clr.AddReference( 'vjslib, Version=2.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a' )
from java.io import *
from java.util.zip import *
from System.IO import *
from System.IO.Compression import *
from System import Array, Byte, SByte, Int64
from System.Text import Encoding

def readFileToSByteArray(name):
  # open a file via Java I/O
  raw = RandomAccessFile(name, 'r')
  # print "File size in bytes = %d "  % (raw.length())

  # read into signed byte array
  dim = Array[Int64]([raw.length()])
  helper = Array[SByte]([0])
  buffer = Array.CreateInstance(helper[0].GetType(), dim)
  raw.readFully(buffer)
  raw.close()
  return buffer
  
def sbyteArrayToUbyteArray(buffer, offset=0, length=-1):
  if length < 0:
    length = buffer.Length
 
  dim = Array[Int64]([length])
  helper = Array[Byte]([0])
  ubuffer = Array.CreateInstance(helper[0].GetType(), dim)
  
  # copy into unsigned byte array
  for i in range(0,length):
    ubuffer[i] = buffer[i+offset] & 0xff
  return ubuffer
  
def jdeflate(buffer):
  sink0 = ByteArrayOutputStream()
  sink = DeflaterOutputStream(sink0)
  sink.write(buffer, 0, buffer.Length)
  sink.close()
  sink0.close()
  return sink0.toByteArray()
  
def update_adler(adler, buffer):
  s1 = adler & 0xffff
  s2 = (adler >> 16) & 0xffff
  BASE = 65521
  for n in range(0,buffer.Length):
          s1 = (s1 + buffer[n]) % BASE
          s2 = (s2 + s1)     % BASE
  return (s2 << 16) + s1
  
def ninflate(buffer):
  mem = MemoryStream(buffer)
  inflate = DeflateStream(mem, CompressionMode.Decompress)

  mem = MemoryStream()
  while True:
    x = inflate.ReadByte()
    if x < 0:
      break
    mem.WriteByte(x)
 
  inflate.Close()
  mem.Close()
  return mem.ToArray()
  
 
##==========================================

# select a file
name = ...

# make signed, unsigned buffers and string
buffer = readFileToSByteArray(name)
print "Constructed buffer size %d" % (buffer.Length)
ubuffer = sbyteArrayToUbyteArray(buffer)
instring = Encoding.Default.GetString(ubuffer)

# compute the Adler32 checksum
adler = update_adler(1, ubuffer)
print "Adler32 = %d" % (adler)
 
# deflate in Java
deflated = jdeflate(buffer)

# check the ZLIB header -- expect 120, 156 actually (120,-100)
first = (deflated[0] & 0xff)
second = (deflated[1] & 0xff)
print "header value EXPECTED 120:156 ACTUAL %d:%d" % (first, second)

i = deflated.Length-4
x = ((deflated[i]&0xff) << 24) | ((deflated[i+1]&0xff) << 16) | ((deflated[i+2]&0xff) << 8) | (deflated[i+3]&0xff)
print "Java Adler32 = %d" % (x)

# discard header and Adler32 tail
newbuffer = sbyteArrayToUbyteArray(deflated, 2, deflated.Length-6)
print "ZLIB length %d" % (deflated.Length)
print "deflate section length %d" % (newbuffer.Length)

# reflate
out = ninflate(newbuffer)

# compare with input
print "reflated buffer length : %d" % (out.Length)
outstring = Encoding.Default.GetString(out)
same = outstring.Equals(instring)
print "Output == Input ?? %s" %(str(same))

That works fine; but the converse, taking a .Net deflate and adding the appropriate top and tail took a bit of getting to work.

First pitfall -- the InflaterInputStream has to be read in chunks as large as feasible, rather than byte at a time, so as not to throw a premature EOFException. That overcome, I got a result of the right length, but differing in the final few characters for the file under test, which I resolved by doing a belt-and-braces closing of the deflate operation. The un-refactored code I currently have continues from the above as:

# now the other way around
sink0 = MemoryStream()
sink = DeflateStream(sink0, CompressionMode.Compress)
sink.Write(ubuffer, 0, ubuffer.Length)
## overkill the flush and close here
sink.Flush()
sink.Close()
sink0.Flush()
sink0.Close()

deflated = sink0.ToArray()
print "deflate section length %d" % (deflated.Length)

#now inflate
dim = Array[Int64]([deflated.Length+6])
jbuffer = Array.CreateInstance(buffer[0].GetType(), dim)

jbuffer[0] = 120 # 0111 0100 = 120 : 32 kbit window, Deflate
jbuffer[1] = -100 # 10 0 ????? = 128 + x : default compress, no dict, checksum

def sbyte(x):
  y = x & 0xff
  if y > 127:
    return y - 256
  return y
 
for i  in range(0,deflated.Length):
    jbuffer[i+2] = sbyte(deflated[i])
 
i = deflated.Length+2
jbuffer[i] = sbyte(adler>>24) 
jbuffer[i+1] = sbyte(adler>>16) 
jbuffer[i+2] = sbyte(adler>>8)
jbuffer[i+3] = sbyte( adler )
 
 
source0 = ByteArrayInputStream(jbuffer)
source = InflaterInputStream(source0)

dim = Array[Int64]([ubuffer.Length])
helper = Array[SByte]([0])
xbuffer = Array.CreateInstance(helper[0].GetType(), dim)

## take big bites
offset = 0
try:
 while True:
  x = source.read(xbuffer, offset, xbuffer.Length-offset)
  if x < 0:
    break
  offset += x
except EOFException:
  pass

reflated = sbyteArrayToUbyteArray(xbuffer)

print "reflated length is %d" % (reflated.Length)
outstring = Encoding.Default.GetString(reflated)

same = outstring.Equals(instring)
print same

This should allow me to simplify the baggage accumulated for the C#/Erlang bridge, which currently uses a second-generation port of the original 'C' ZLIB for this sort of interoperation.

Much Later — I have ported this to F# on .net 4.5.



There's a lot of buffer to stream to buffer conversion involved -- the {n,j}{in,de}flate functions are just that. It's ndeflateZLIB, ninflateZLIBFull that do the complete transformation from a byte array to a compressed byte array and back again. The sbyte bit is purely a J# compatibility thing. Full solution here.

Sunday 22 March 2009

Belatedly, more IronPython + Silverlight

Domestic happenings and the demands of the day-job have kept me away from the codeface for playtime for a while; but at last, following up from last year, a SilverLight2/IronPython2 orrery-clock. Back-ported from F#, I confess, hence the possibly less than Pythonic idioms at times.

Sunday 11 January 2009

Python swinging both ways

Following up to the last post I made in my quest for a cross-VM (JVM and CLR), single code-base, polyglot language stack, which doesn't involve any more Java than can be helped. Especially when there is Scala to play with, a language which a reading of the stairway book shows is very nifty indeed.

To summarise where we are, and what we have discovered to date --

  • Python can call Scala and Java happily
  • Java calling into Python is funky and platform dependent; doubly so for Scala
  • Scala cannot both call into java.* classes and compile on .net
  • Low-level Scala pre-defs differ in the Byte type (signed in Java/J#/Scala-JVM, unsigned in Scala-msil)
  • Ruby's predilection for Pascal-case namespaces (fudged in JRuby to match Java's lower-case convention) would require a lot of plumbing around in C# to mate IronRuby to J# or Scala-msil (as the rest of .net uses Pascal-casing).

And then there is this weekend's discovery.

As J# is a barely JDK1.2 implementation at best, I can't use the latest Java splash-screen feature, and have to fall back on older implementations. I have one to hand, back from c. JDK 1.4 days. It uses synchronized(), Object.wait() and Object.notifyAll().

The first is easy enough to deal with when wanting to put as much as possible of this GUI-driving code into Python -- define an interface to hold a code block

public interface ISynchronizedAction
{
  void performAction();
}

and then have a class which knows about the object to synchronize on, and can execute the block in a synchronized scope

public class Synchronized {
  private Object lock;

  public Synchronized(Object lock) {this.lock = lock;}

  public void Lock(ISynchronizedAction action)
  {
    synchronized(lock) {action.performAction();}
  }
}

Except in IronPython, I also discover by dumping the dir() of an object sub-classing java.awt.Window -- inheritance being needed for the splash-screen window class rather than composition, in order to hook the update/repaint APIs -- that neither Object.wait() nor Object.notifyAll() are present to be called. Fortunately the object I want these methods on is the same one I want to synchronize on, the splash-screen window itself, so I was able to just extend Synchronized with

  public void delegateWait() throws InterruptedException
  {
    lock.wait();
  }

  public void delegateNotifyAll()
  {
    lock.notifyAll();
  }

and make the there-and-back-again calls as required.

Then I just had to work around the older dialect's lack of support for .png (by using a .gif) by using the handy Java-1.1 compatible javapng-1.3.0 library to actually paint the image into the splash screen.

As usual, Jython needs the helper .jar file in the CLASSPATH, while IronPython can reference the equivalent .dll from code by assembly file name.

Saturday 10 January 2009

Towards Scala/.net 2.0

A propos of my last bit of banging head against a wall... Oh, and these snippets are definitely offered under the WTFPL.

The main things that the scala-msil compilation balks at when looking at .Net assemblies post framework 1.x are generics; and things marked as var. Looking at the source in http://lampsvn.epfl.ch/svn-repos/scala/msil/trunk/src/, the first changes to make are, first in msil/util/Signature.java, add the extra byte code values

    public static final int ELEMENT_TYPE_VAR = 0x13;     // a class type variable VAR
    /***/
    public static final int  ELEMENT_TYPE_GENERICINST    = 0x15;     // GENERICINST    ...

and then start to do something about parsing them in msil/PEFile.java, in method PEFile.Sig.decodeType0()

        case ELEMENT_TYPE_GENERICINST:
        // Followed by <type> token
        //ELEMENT_TYPE_GENERICINST <an mdTypeDef metadata token> <argument Count> <arg1> ... <argN>
        {
            // base type
            int tmp = readByte();
            if((tmp != ELEMENT_TYPE_VALUETYPE) && (tmp != ELEMENT_TYPE_CLASS))
                throw new RuntimeException("*1*>> "+ byte2hex(tmp) +
        "@" + pos() + " in " + this);   
            int id = decodeInt();
            type = pemodule.getTypeDefOrRef(id);
            if (type == null)   throw new RuntimeException("**>> "+ byte2hex(desc) +
        "@" + pos() + " in " + this);
            // number of type arguments
            int num = decodeInt();
            System.out.println("num = "+num);
            for(int i=0;i<num;++i)
            {
                Type t = decodeType0();
                //TODO: use this information
            }
        }
        break;

        case ELEMENT_TYPE_VAR:
        {
            int index = decodeInt();
            System.out.println("var of type "+index);
            // TODO: actually look up what the index means 
            return Type.GetType("System.Object");
        }

This is necessary but not sufficient -- this still leaves problems with types involving templated subtypes or interfaces, for which the first TODO is probably meaningful. As a consequence we're still a long way from a "hello .net 2.0 world!" example yet; let alone a rebuilt scala-compiler.jar, alas.