2012-06-21

HotSpot bug in Java 7u4, 7u5, 7u6(rc) with StringBuilder optimisation

I found an odd bug that seems to be related with the new Java7 optimisations regarding StringBuilder concatenation. The following code works, until HotSpot kicks in, and replaces the interpreted code with optimized code, after a few thousand iterations.

Code that corrupts the concatenated string when compiled with Eclipse:
public class Main {
 
        public static void main(String[] args) throws Exception {
 
                System.out.println("Java Version: " + System.getProperty("java.vm.version"));
 
                long[] durations = new long[60];
 
                for (int i = 0; true; i++) {

                        // this empty for-loop is required to reproduce this bug 
                        for (long duration : durations) {
                                // do nothing
                        }
 
                        {
                                String s = "test";
                                int len = s.length();
 
                                s = s + s;
                                len = len + len;
 
                                s = s + s;
                                len = len + len;
 
                                s = s + s;
                                len = len + len;
 
                                if (s.length() != len) {
                                        System.out.println("Failed at iteration: " + i);
                                        System.out.println("Length mismatch: " + s.length() + " <> " + len);
                                        System.out.println("Expected: \"" + "test" + "test" + "test" + "test" + "test" + "test" + "test" + "test" + "\"");
                                        System.out.println("Actual:   \"" + s + "\"");
                                        System.exit(0);
                                }
                        }
                }
        }
}


Code that corrupts the concatenated string when compiled with Javac:
public class Main {
 
        public static void main(String[] args) throws Exception {
 
                System.out.println("Java Version: " + System.getProperty("java.vm.version"));
 
                long[] durations = new long[60];
 
                for (int i = 0; true; i++) {
 
                        // this empty for-loop is required to reproduce this bug
                        for (long duration : durations) {
                                // do nothing
                        }
 
                        {
                                String s = "test";
                                int len = s.length();
 
                                s = new StringBuilder(String.valueOf(s)).append(s).toString();
                                len = len + len;
 
                                s = new StringBuilder(String.valueOf(s)).append(s).toString();
                                len = len + len;
 
                                s = new StringBuilder(String.valueOf(s)).append(s).toString();
                                len = len + len;
 
                                if (s.length() != len) {
                                        System.out.println("Failed at iteration: " + i);
                                        System.out.println("Length mismatch: " + s.length() + " <> " + len);
                                        System.out.println("Expected: \"" + "test" + "test" + "test" + "test" + "test" + "test" + "test" + "test" + "\"");
                                        System.out.println("Actual:   \"" + s + "\"");
                                        System.exit(0);
                                }
                        }
                }
        }
}


Output:
Java Version: 23.0-b21
Failed at iteration: 11983
Length mismatch: 16 <> 32
Expected: "testtesttesttesttesttesttesttest"
Actual:   "nullnulltesttest"

2012-02-10

Bash script for simple port-knocking in iptables

This is a simple bash script that allows you to add (multiple) port-knocking rules into iptables. Usage is explained below.
KNOCK_NAME=$1

PORT_1=$2
PORT_2=$3
PORT_3=$4
PORT_4=$5

OPEN_PORT=$6
OPEN_TIME=$7




PHASE_1=p1_$KNOCK_NAME
PHASE_2=p2_$KNOCK_NAME
PHASE_3=p3_$KNOCK_NAME
PHASE_4=p4_$KNOCK_NAME

JUMP_TO_2=j2_$KNOCK_NAME
JUMP_TO_3=j3_$KNOCK_NAME
JUMP_TO_4=j4_$KNOCK_NAME


iptables -X $JUMP_TO_2
iptables -N $JUMP_TO_2
iptables -A $JUMP_TO_2 -m recent --name $PHASE_1 --remove
iptables -A $JUMP_TO_2 -m recent --name $PHASE_2 --set

iptables -X $JUMP_TO_3
iptables -N $JUMP_TO_3
iptables -A $JUMP_TO_3 -m recent --name $PHASE_2 --remove
iptables -A $JUMP_TO_3 -m recent --name $PHASE_3 --set

iptables -X $JUMP_TO_4
iptables -N $JUMP_TO_4
iptables -A $JUMP_TO_4 -m recent --name $PHASE_3 --remove
iptables -A $JUMP_TO_4 -m recent --name $PHASE_4 --set


iptables -A INPUT                        -m recent --update --name $PHASE_1
iptables -A INPUT -p udp --dport $PORT_1 -m recent --set    --name $PHASE_1
iptables -A INPUT -p udp --dport $PORT_2 -m recent --rcheck --name $PHASE_1 -j $JUMP_TO_2
iptables -A INPUT -p udp --dport $PORT_3 -m recent --rcheck --name $PHASE_2 -j $JUMP_TO_3
iptables -A INPUT -p udp --dport $PORT_4 -m recent --rcheck --name $PHASE_3 -j $JUMP_TO_4

iptables -A INPUT -p tcp --dport $OPEN_PORT -m recent --rcheck --seconds $OPEN_TIME --name $PHASE_4 -j ACCEPT
(credit: http://www.debian-administration.org/articles/268)

In this example I'm actually using UDP ports, because they are easier to knock on: no attempt is made to actually connect and (thus) timeout. If you prefer TCP knocking, and you don't know how to adjust the script, click here.


# setup all rules you currently have
... (important stuff!)

# add (several) port knocking triggers
./iptables-knocking.sh mail2 108 107 106 105 9992 15
./iptables-knocking.sh mail3 101 102 103 104 9993 15
                         |    |   |   |   |   |   -> timeout_to_close
                       name   |   | port3 | port_to_open
                            port1 |       |
                               port2    port4

# reject everything else
iptables -A INPUT -s 0/0 -d 0/0 -j REJECT

When working with IPTABLES, keep paying attention. It's WAY too easy to lock yourself out or 'ruin your uptime' one way or another. Needless to say, I am in no way responsible for any problems or damages that are the result of the usage of the above code. You have been warned.


Next up, a trivial Java portknocking client:
public static void knockUDP(String hostname, int... ports) {
    DatagramSocket socket = new DatagramSocket();
    for(int port: ports) {

       // account for a bit of packet loss
       for(int i=0; i<4; i++) {
          socket.send(new DatagramPacket(new byte[1], 1, new InetSocketAddress(hostname, port)));
       }

       // try to make it more likely the packets arrive in-order
       Thread.sleep(100);
    }
}

public static void knockTCP(String hostname, int... ports) {
    for(int port: ports) {
       Socket s = new Socket();
       try {
          s.connect(new InetSocketAddress(hostname, port), 100);
          s.close(); // it appears we actually connected, which is not what we wanted....
       } catch( IOException) {
          // ignore, really!
       }
    }
}

knockUDP("your-public-server.com", 101, 102, 103, 104);
knockTCP("your-public-server.com", 101, 102, 103, 104);

Reverse SSH tunnel in plain english...

Those tutorials explaining reverse SSH tunnels are ambiguous at best in their examples, often using the same port number twice, making it unclear whether it is a local port or a remote port.

Yes, I'm done complaining, here's my attempt at being helpful:

MASTER_HOST=where-your-ssh-server-is.com
MASTER_PORT=22 # likely
MASTER_USER=root # not really!
MASTER_LISTEN=... # whatever you want your public port to be
TARGET_HOST=192.168.... # probably some local server
TARGET_PORT=25 # let's imagine we tunnel a mailserver

# let's actually do something now!
ssh -l $MASTER_USER -nNT -p $MASTER_PORT -R $MASTER_LISTEN:$TARGET_HOST:$TARGET_PORT $MASTER_HOST

Please ensure the line 
   GatewayPorts yes
exists in the file
   /etc/ssh/sshd_config
or your tunnel will bind to localhost only.


As you can see, the order of parameters is not quite intuitive, which might have brought you on this page in the first place. Enjoy.

2010-11-30

Java Continuations and Green Threads at native speeds

Continuations, or green threads, are a concept mostly seen in scripting languages. Green threads are just like native threads, but you can run multiple of them on a single native thread. Java has no native support for continuations, so we have to transform (instrument) java bytecode with a library that saves localvars and the instruction pointer upon a GreenThread.yield(). Once the green thread is resumed, this information is used to rebuild the stacktrace, with all localvars intact.

The library used is: http://l33tlabs.org/Continuations/ written by Matthias Mann
His library depends on ASM3 to parse and construct the bytecode: http://asm.ow2.org/

Through the Java Instrumentation Agent that I wrote for the previously mentioned library, there is no need to transform your byteclass ahead of time. The java agent will take care of this at runtime.

java -javaagent:conti4.jar -cp ./your.jars your.MainClass


I wrote a wrapper around the continuation library, to lower the bar a bit. I hope the code pretty much speaks for itself, and if not, feel free to ask questions. For additional convenience, I added some demo code and its fascinating output at the bottom.

Enjoy!
import de.matthiasmann.continuations.Coroutine;
import de.matthiasmann.continuations.CoroutineProto;
import de.matthiasmann.continuations.SuspendExecution;
import de.matthiasmann.continuations.Coroutine.State;

/*
 * Created on Nov 30, 2010
 * 
 * @author Riven
 */

public abstract class GreenThread implements CoroutineProto
{
   public static final long EOF = -1L;

   private final Coroutine  coroutine;

   public GreenThread()
   {
      this.coroutine = new Coroutine(this);
   }

   private long doSleep;

   @Override
   // this is where you put your code
   public abstract void coExecute() throws SuspendExecution;

   long step()
   {
      coroutine.run();
      if (coroutine.getState() == State.FINISHED)
         return EOF;
      return this.doSleep;
   }

   public static void yield() throws SuspendExecution
   {
      GreenThread.sleep(0L);
   }

   public static void sleep(long ms) throws SuspendExecution
   {
      GreenThread thread = (GreenThread) Coroutine.getActiveCoroutine().getProto();

      thread.doSleep = Math.max(ms, 0L);

      Coroutine.yield();
   }
}



---------------------------------------------------------------------

import java.util.Comparator;
import java.util.PriorityQueue;

/*
 * Created on Nov 30, 2010
 * 
 * @author Riven
 */

public class GreenThreadQueue
{
   private final PriorityQueue queue;
   private final List          reschedule;

   public GreenThreadQueue()
   {
      this.queue = new PriorityQueue(16, new GreenThreadWakeupComparator());
      this.reschedule = new ArrayList();
   }

   public void start(GreenThread thread)
   {
      this.queue.add(new GreenThreadWakeup(thread, 0L));
   }

   public boolean tick(long now)
   {
      try
      {
         while (true)
         {
            GreenThreadWakeup wakeup = this.queue.peek();
            if (wakeup == null)
               return !this.reschedule.isEmpty(); // signal nothing more to do

            if (wakeup.timestamp > now)
               break;

            if (this.queue.poll() != wakeup)
               throw new IllegalStateException();

            long sleep = wakeup.thread.step();
            if (sleep == GreenThread.EOF)
               continue;

            wakeup.timestamp = now + sleep;
            this.reschedule.add(wakeup);
         }

         return true;
      }
      finally
      {
         for (GreenThreadWakeup wakeup : this.reschedule)
         {
            this.queue.add(wakeup);
         }
         this.reschedule.clear();
      }
   }

   static private class GreenThreadWakeup
   {
      public final GreenThread thread;
      public long              timestamp;

      public GreenThreadWakeup(GreenThread thread, long timestamp)
      {
         this.thread = thread;
         this.timestamp = timestamp;
      }
   }

   static class GreenThreadWakeupComparator implements Comparator
   {
      @Override
      public int compare(GreenThreadWakeup o1, GreenThreadWakeup o2)
      {
         int val = Long.signum(o1.timestamp - o2.timestamp);
         return (val == 0) ? 1 : val;
      }
   }
}



Demo code
GreenThreadQueue queue = new GreenThreadQueue();

      GreenThread thread1 = new GreenThread()
      {
         @Override
         public void coExecute() throws SuspendExecution
         {
            for (int i = 0; i < 3; i++)
            {
               System.out.println("a" + i);
               GreenThread.sleep(1500);
            }
         }
      };

      GreenThread thread2 = new GreenThread()
      {
         @Override
         public void coExecute() throws SuspendExecution
         {
            for (int i = 0; i < 4; i++)
            {
               System.out.println("b" + i);
               GreenThread.sleep(1300);
            }
         }
      };

      queue.start(thread1);
      queue.start(thread2);

      do
      {
         try { Thread.sleep(100); } catch(InterruptedException exc) { /* ignore */ }
      }
      while (queue.tick(System.currentTimeMillis()));
   }
Fancy output (from 1 thread)
a0
b0
b1
a1
b2
a2
b3

2010-11-24

Lost four words... (pro nouns)

It got cold while she called for juice from , not awaiting the tide and tied a tight knot. A scene never seen again, maybe missed due to the dew or mist on site by a dude with poor sight on one side. A phase etched on the edge of his face. Whether her patients had patience depended on the weather. So take a look at the sea and see: sow and pour it in a poor pore, with any luck, lock it. I'll weigh the way the rained isle was reigned. A pane hid me, then a pain hit me. During the war the witch wore a hat which was won by one bright bride. During the juring descent, she thought and fought the scent. Worn by the sun, I warn my son, as his eye tans tense, 'caus where regular wear hides hides, I knew a new gnu (its dead dad had that dept) that played ball, sipping a bowl for four hours, assuming it was ours, while the cued cheap cute sheep queued. Silence. Deaf by impending death. 'Hear here', she heard hurt. She waited, weighted by lead, led down the stairs by the wrath filled failed ref. Bye Susan, by all means, awe at the whirled world... Eight dodo's ate dough though.

cold/called
juice/
not/knot
tide/tight/tied
scene/seen
missed/mist
due/dew
site/side/sight
phase/face
etch/edge

whether/weather
patience/patients
suck it/socket
rained/reighed
thought/fought
eight/ate
dodo/though/dough
so/sow
luck/lock
sea/see
pour/pore/poor

war/wore
won/one
witch/which
bright/bride
worn/warn
sun/son
tans/tense
where/wear
knew/new/gnu
dead/dad/that/dept
descent/the scent

ball/bowl
for/four
hours/ours
cued/cute/queued
cheap/sheep
plug/plaque
deaf/death
hear/here
heard/hurt
waited/weighted

lead/led
wrath/ref
filled/failed
bye/by
all/awe
whirled/world
i'll/isle
way/weigh
pain/pane
hit/hid
Disclaimer: English is not my native language, so certain words might sound the same for me, while they are clearly distinct for you gays.

2010-08-19

Calculate PerlinNoise faster with an optimization to grad()

A simple optimization to the gradient function makes the noise function twice as fast.

PerlinNoise.grad()
inline float grad(int hash, float x, float y, float z)
   {  
 //float u = (h < 8) ? x : y;
 //float v = (h < 4) ? y : ((h == 12 || h == 14) ? x : z);
 //return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);

 switch(hash & 0xF)
 {
  case 0x0: return  x + y;
  case 0x1: return -x + y;
  case 0x2: return  x - y;
  case 0x3: return -x - y;
  case 0x4: return  x + z;
  case 0x5: return -x + z;
  case 0x6: return  x - z;
  case 0x7: return -x - z;
  case 0x8: return  y + z;
  case 0x9: return -y + z;
  case 0xA: return  y - z;
  case 0xB: return -y - z;
  case 0xC: return  y + x;
  case 0xD: return -y + z;
  case 0xE: return  y - x;
  case 0xF: return -y - z;
  default: return 0; // never happens
 }
   }

PerlinNoise.noise() (click code to expand)
int   perm[512];

   void initPerlinNoise()
   {
      int i, permutation[] = { 151, 160, 137, 91, 90, 15, 131, 13, 201, 95, 96, 53, 194, 233, 7, 225, 140, 36, 103, 30, 69, 142, 8, 99, 37, 240, 21, 10, 23, 190, 6, 148, 247, 120, 234, 75, 0, 26, 197, 62, 94, 252, 219, 203, 117, 35, 11, 32, 57, 177, 33, 88, 237, 149, 56, 87, 174, 20, 125, 136, 171, 168, 68, 175, 74, 165, 71, 134, 139, 48, 27, 166, 77, 146, 158, 231, 83, 111, 229, 122, 60, 211, 133, 230, 220, 105, 92, 41, 55, 46, 245, 40, 244, 102, 143, 54, 65, 25, 63, 161, 1, 216, 80, 73, 209, 76, 132, 187, 208, 89, 18, 169, 200, 196, 135, 130, 116, 188, 159, 86, 164, 100, 109, 198, 173, 186, 3, 64, 52, 217, 226, 250, 124, 123, 5, 202, 38, 147, 118, 126, 255, 82, 85, 212, 207, 206, 59, 227, 47, 16, 58, 17, 182, 189, 28, 42, 223, 183, 170, 213, 119, 248, 152, 2, 44, 154, 163, 70, 221, 153, 101, 155, 167, 43, 172, 9, 129, 22, 39, 253, 19, 98, 108, 110, 79, 113, 224, 232, 178, 185, 112, 104, 218, 246, 97, 228, 251, 34, 242, 193, 238, 210, 144, 12, 191, 179, 162, 241, 81, 51, 145, 235, 249,
         14, 239, 107, 49, 192, 214, 31, 181, 199, 106, 157, 184, 84, 204, 176, 115, 121, 50, 45, 127, 4, 150, 254, 138, 236, 205, 93, 222, 114, 67, 29, 24, 72, 243, 141, 128, 195, 78, 66, 215, 61, 156, 180 };

      for (i = 0; i < 256; i++)
         perm[256 + i] = perm[i] = permutation[i];
   }


   inline float fade(float t)
   {
      return t * t * t * (t * (t * 6.0f - 15.0f) + 10.0f);
   }

   inline float lerp(float t, float a, float b)
   {
      return a + t * (b - a);
   }

   inline float grad(int hash, float x, float y, float z)
   {  
 //float u = (h < 8) ? x : y;
 //float v = (h < 4) ? y : ((h == 12 || h == 14) ? x : z);
 //return ((h & 1) == 0 ? u : -u) + ((h & 2) == 0 ? v : -v);

 switch(hash & 0xF)
 {
  case 0x0: return  x + y;
  case 0x1: return -x + y;
  case 0x2: return  x - y;
  case 0x3: return -x - y;
  case 0x4: return  x + x;
  case 0x5: return -x + x;
  case 0x6: return  x - x;
  case 0x7: return -x - x;
  case 0x8: return  y + x;
  case 0x9: return -y + x;
  case 0xA: return  y - x;
  case 0xB: return -y - x;
  case 0xC: return  y + z;
  case 0xD: return -y + x;
  case 0xE: return  y - x;
  case 0xF: return -y - z;
  default: return 0; // never happens
 }
   }

   static inline float __fastcall noise(float x, float y, float z)
   {
      jint ix,iy,iz,gx,gy,gz;
      jint a0,b0,aa,ab,ba,bb;

      float aa0,ab0,ba0,bb0;
      float aa1,ab1,ba1,bb1;
      float a1,a2,a3,a4,a5,a6,a7,a8;
      float u,v,w,a8_5,a4_1;

      ix = (jint)x; x-=ix;
      iy = (jint)y; y-=iy;
      iz = (jint)z; z-=iz;

      gx = ix & 0xFF;
      gy = iy & 0xFF;
      gz = iz & 0xFF;
      
      a0 = gy+perm[gx];
      b0 = gy+perm[gx + 1];
      aa = gz+perm[a0];
      ab = gz+perm[a0 + 1];
      ba = gz+perm[b0];
      bb = gz+perm[b0 + 1];

      aa0 = perm[aa]; aa1 = perm[aa + 1];
      ab0 = perm[ab]; ab1 = perm[ab + 1];
      ba0 = perm[ba]; ba1 = perm[ba + 1];
      bb0 = perm[bb]; bb1 = perm[bb + 1];

      a1 = grad(bb1, x-1, y-1, z-1);
      a2 = grad(ab1, x  , y-1, z-1);
      a3 = grad(ba1, x-1, y  , z-1);
      a4 = grad(aa1, x  , y  , z-1);
      a5 = grad(bb0, x-1, y-1, z  );
      a6 = grad(ab0, x  , y-1, z  );
      a7 = grad(ba0, x-1, y  , z  );
      a8 = grad(aa0, x  , y  , z  );

      u = fade(x);
      v = fade(y);
      w = fade(z);

      a8_5 = lerp(v, lerp(u, a8, a7), lerp(u, a6, a5));
      a4_1 = lerp(v, lerp(u, a4, a3), lerp(u, a2, a1));
      return lerp(w, a8_5, a4_1);
   }

2010-07-23

Rhino ClassShutter replacement: SandboxShutter

Because the ClassShutter in Rhino doesn't usually provide enough information to make decisions on whether or not certain Java objects, fields or methods should be accessible, I wrote the SandboxShutter which will enable you to control accessibility for each field and each method of each Java object. The performance impact is negligible, because JavaScript itself is an order of magnitude slower than the injected checks.


The SandboxShutter interface:
public interface SandboxShutter
{
   public boolean allowClassAccess(Class<?> type);

   public boolean allowFieldAccess(Class<?> type, Object instance, String fieldName);

   public boolean allowMethodAccess(Class<?> type, Object instance, String methodName);

   public boolean allowStaticFieldAccess(Class<?> type, String fieldName);

   public boolean allowStaticMethodAccess(Class<?> type, String methodName);
}


When the following javascript code is executed:
importPackage(Packages.my.game); // assuming the Java class my.game.Player exists

var player = new Player("Jake");
player.gender = "female"; // this is a Java method!
player.setGender("male"); // this the same Java method.
player.age = 18; // this is a Java field
player.age += 3;

var player = new Player("Jane");
player.gender = "male";
player.gender = "female";
player.age = 19;
player.age += 2;

var count = Player.PLAYER_COUNT;
Player.PLAYER_COUNT += 2;


The following SandboxShutter calls will be made:
allowClassAccess:       my.game.Player

allowMethodAccess:      my.game.Player.setGender() instance=Player@2346
allowFieldAccess:       my.game.Player.age         instance=Player@2346

allowMethodAccess:      my.game.Player.setGender() instance=Player@54326
allowFieldAccess:       my.game.Player.age         instance=Player@54326

allowStaticFieldAccess: my.game.Player.PLAYER_COUNT
As shown, there will be at most one call for each field/method in each object, and one call per class. This allows you to control accessibility per Java object.


Create the SandboxContextFactory:
   public static class SandboxContextFactory extends ContextFactory
   {
      final SandboxShutter shutter;

      public SandboxContextFactory(SandboxShutter shutter)
      {
         this.shutter = shutter;
      }

      @Override
      protected Context makeContext()
      {
         Context cx = super.makeContext();
         cx.setWrapFactory(new SandboxWrapFactory());
         cx.setClassShutter(new ClassShutter()
         {
            private final Map<String, Boolean> nameToAccepted = new HashMap<String, Boolean>();

            @Override
            public boolean visibleToScripts(String name)
            {
               Boolean granted = this.nameToAccepted.get(name);

               if (granted != null)
               {
                  return granted.booleanValue();
               }

               Class< ? > staticType;
               try
               {
                  staticType = Class.forName(name);
               }
               catch (Exception exc)
               {
                  this.nameToAccepted.put(name, Boolean.FALSE);
                  return false;
               }

               boolean grant = shutter.allowClassAccess(staticType);
               this.nameToAccepted.put(name, Boolean.valueOf(grant));
               return grant;
            }
         });
         return cx;
      }

      class SandboxWrapFactory extends WrapFactory
      {
         @Override
         public Scriptable wrapNewObject(Context cx, Scriptable scope, Object obj)
         {
            this.ensureReplacedClass(scope, obj, null);

            return super.wrapNewObject(cx, scope, obj);
         }

         @Override
         public Object wrap(Context cx, Scriptable scope, Object obj, Class< ? > staticType)
         {
            this.ensureReplacedClass(scope, obj, staticType);

            return super.wrap(cx, scope, obj, staticType);
         }

         @Override
         public Scriptable wrapAsJavaObject(Context cx, Scriptable scope, Object javaObject, Class< ? > staticType)
         {
            final Class< ? > type = this.ensureReplacedClass(scope, javaObject, staticType);

            return new NativeJavaObject(scope, javaObject, staticType)
            {
               private final Map<String, Boolean> instanceMethodToAllowed = new HashMap<String, Boolean>();

               @Override
               public Object get(String name, Scriptable scope)
               {
                  Object wrapped = super.get(name, scope);

                  if (wrapped instanceof BaseFunction)
                  {
                     String id = type.getName() + "." + name;
                     Boolean allowed = this.instanceMethodToAllowed.get(id);

                     if (allowed == null)
                     {
                        boolean allow = shutter.allowMethodAccess(type, javaObject, name);
                        this.instanceMethodToAllowed.put(id, allowed = Boolean.valueOf(allow));
                     }

                     if (!allowed.booleanValue())
                     {
                        return NOT_FOUND;
                     }
                  }
                  else
                  {
                     // NativeJavaObject + only boxed primitive types?
                     if (!shutter.allowFieldAccess(type, javaObject, name))
                     {
                        return NOT_FOUND;
                     }
                  }

                  return wrapped;
               }
            };
         }

         //

         private final Set<Class< ? >> replacedClasses = new HashSet<Class< ? >>();

         private Class< ? > ensureReplacedClass(Scriptable scope, Object obj, Class< ? > staticType)
         {
            final Class< ? > type = (staticType == null && obj != null) ? obj.getClass() : staticType;

            if (!type.isPrimitive() && !type.getName().startsWith("java.") && this.replacedClasses.add(type))
            {
               this.replaceJavaNativeClass(type, scope);
            }

            return type;
         }

         private void replaceJavaNativeClass(final Class< ? > type, Scriptable scope)
         {
            Object clazz = Context.jsToJava(ScriptableObject.getProperty(scope, "Packages"), Object.class);
            Object holder = null;
            for (String part : Text.split(type.getName(), '.'))
            {
               holder = clazz;
               clazz = ScriptableObject.getProperty((Scriptable) clazz, part);
            }
            NativeJavaClass nativeClass = (NativeJavaClass) clazz;

            nativeClass = new NativeJavaClass(scope, type)
            {
               @Override
               public Object get(String name, Scriptable start)
               {
                  Object wrapped = super.get(name, start);

                  if (wrapped instanceof BaseFunction)
                  {
                     if (!shutter.allowStaticMethodAccess(type, name))
                     {
                        return NOT_FOUND;
                     }
                  }
                  else
                  {
                     // NativeJavaObject + only boxed primitive types?
                     if (!shutter.allowStaticFieldAccess(type, name))
                     {
                        return NOT_FOUND;
                     }
                  }

                  return wrapped;
               }
            };

            ScriptableObject.putProperty((Scriptable) holder, type.getSimpleName(), nativeClass);
            ScriptableObject.putProperty(scope, type.getSimpleName(), nativeClass);
         }
      }
   }


Install the (global) SandboxContextFactory:
      ContextFactory.initGlobal(new SandboxContextFactory(new SandboxShutter()
      {
         ...
      }));

      // create and initialize Rhino Context
      Context cx = Context.enter();
      Scriptable prototype = cx.initStandardObjects();
      Scriptable topLevel = new ImporterTopLevel(cx);
      prototype.setParentScope(topLevel);
      Scriptable scope = cx.newObject(prototype);
      scope.setPrototype(prototype);

      // your scripts

2010-07-20

Functions on Iterables :: Consume

public class Functional
{
   /**
    * Consumes (removes) all items while iterating
    */

   public static <T> Iterable<T> consume(final Iterable<T> iterable)
   {
      if (iterable == null)
         throw new NullPointerException();

      return new Iterable<T>()
      {
         @Override
         public Iterator<T> iterator()
         {
            final Iterator<T> iterator = iterable.iterator();

            return new Iterator<T>()
            {
               @Override
               public boolean hasNext()
               {
                  return iterator.hasNext();
               }

               @Override
               public T next()
               {
                  T result = iterator.next();
                  iterator.remove();
                  return result;
               }

               @Override
               public void remove()
               {
                  throw new NoSuchElementException("already removed");
               }
            };
         }
      };
   }




To remove all short texts in a list:
List<String> data = ...;

Filter<String> shortText = new Filter<String>()
{
   public boolean accept(String item) { return item == null || item.length() <= 3; }
}

for(String item: consume(filter(data, shortText)))
{
   System.out.println("By the time you see this, '"+item+"' has been removed.");
}

Functions on Iterables :: Event Hooks

public interface Operator
{
   public void operate(T item);
}

public class Functional
{
   /**
    * Performs a callback on each element-visit, and each element removal
    */

    public static <T> Iterable<T> eventHook(final Iterable<T> iterable,
                                            final Operator<T> onVisit,
                                            final Operator<T> onRemove)
   {
      if (iterable == null)
         throw new NullPointerException();
      if (onVisit == null && onRemove == null)
         throw new NullPointerException("must specify either onVisit, onRemove or both");

      return new Iterable<T>()
      {
         @Override
         public Iterator<T> iterator()
         {
            final Iterator<T> iterator = iterable.iterator();

            return new Iterator<T>()
            {
               @Override
               public boolean hasNext()
               {
                  return iterator.hasNext();
               }

               @Override
               public T next()
               {
                  this.current = iterator.next();
                  if (onVisit != null)
                     onVisit.operate(this.current);
                  return this.current;
               }

               @Override
               public void remove()
               {
                  iterator.remove();
                  if (onRemove != null)
                     onRemove.operate(this.current);
               }

               //

               private T current;
            };
         }
      };
   }
}

Example:
Operator<String> onVisit= new Operator<String>()
{
   public void operate(String text)
   {
      System.out.println("visited: "+text);
   }
};

Operator<String> onRemove= new Operator<String>()
{
   public void operate(String text)
   {
      System.out.println("removed: "+text);
   }
};

Iterable<String> data = ...;

for(String item: eventHook(data, onVisit, onRemove))
{
   if(item.length() > String.valueOf(Math.PI))
      System.out.println("this text is longer than PI!");
}


Once you created an Iterable (say, a filtered view on a List) you can iterate over it as often as you want. No need to create a new Iterable.


With the support for closures in Java 7 a lot of the boilerplate code will disappear.

Functions on Iterables :: Transformer

public interface Transformer<I, O>
{
   public O transform(I item);
}

public class Functional
{
   /**
    * Transforms Iterable<I> into Iterable<O> using a Transformer<I, O>
    */

   public static <I, O> Iterable<O> transform(final Iterable<I> iterable,
                                              final Transformer<I, O> transformer)
   {
      if (iterable == null)
         throw new NullPointerException();
      if (transformer == null)
         throw new NullPointerException();

      return new Iterable<O>()
      {
         @Override
         public Iterator<O> iterator()
         {
            final Iterator<I> iterator = iterable.iterator();

            return new Iterator<O>()
            {
               @Override
               public boolean hasNext()
               {
                  return iterator.hasNext();
               }

               @Override
               public O next()
               {
                  return transformer.transform(iterator.next());
               }

               @Override
               public void remove()
               {
                  iterator.remove();
               }
            };
         }
      };
   }
}

Example:
Transformer<String, Integer> textToNumber = new Transformer<String, Integer>()
{
   public Integer transform(String text)
   {
      return Integer.valueOf(text);
   }
};

Iterable<String> data = ...;

for(Integer number: transform(data, textToNumber))
{
   System.out.println("number: "+number.intValue());
}

Functions on Iterables :: Filter

Functional programming has its strengths when iterating over data. If you want a view on a subset data, you can make a filter, and iterate over your data only seeing the elements that the filter accepted:

public interface Filter<T>
{
   public boolean accept(T value);
}

public class Functional
{
   /**
    * Filter items from the view of the returned Iterable<T>
    */

   public static <T> Iterable<T> filter(final Iterable<T> iterable, final Filter<T> filter)
   {
      if (iterable == null)
         throw new NullPointerException();
      if (filter == null)
         throw new NullPointerException();

      return new Iterable<T>()
      {
         @Override
         public Iterator<T> iterator()
         {
            final Iterator<T> iterator = iterable.iterator();

            return new Iterator<T>()
            {
               @Override
               public boolean hasNext()
               {
                  this.ensureReady();
                  return this.ready;
               }

               @Override
               public T next()
               {
                  this.ensureReady();
                  if (!this.ready)
                     throw new NoSuchElementException();

                  T result = this.current;
                  this.ready = false;
                  this.current = null;
                  return result;
               }

               @Override
               public void remove()
               {
                  iterator.remove();
               }

               //

               private boolean ready = false;
               private T       current;

               private void ensureReady()
               {
                  while (!this.ready && iterator.hasNext())
                  {
                     T item = iterator.next();
                     if (!filter.accept(item))
                        continue;

                     this.ready = true;
                     this.current = item;
                  }
               }
            };
         }
      };
   }
}

Example:
Filter<String> nonNull = new Filter<String>()
{
   public boolean accept(String value)
   {
      return value != null;
   }
};

Iterable<String> data = ...;

for(String item: filter(data, nonNull))
{
   System.out.println("item: "+item); // guaranteed not to be null
}

2010-04-29

Histogram :: array based

For any reasonably sized Histogram, you probably want to look at this Histogram class based on a HashMap. However, if your histograms are tiny, say, less than 8 elements occur frequently, this array based histogram is an order of magnitude faster.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.NoSuchElementException;

public class TinyHistogram<T>
{
   private T[]   items;
   private int[] usage;
   private int   size;

   public TinyHistogram()
   {
      this.items = (T[]) new Object[4];
      this.usage = new int[4];
      this.size = 0;
   }

   public int put(T item)
   {
      if (item == null)
         throw new IllegalArgumentException();

      int io = this.indexOfItem(item);

      if (io != -1)
      {
         int result = ++this.usage[io];
         this.swapIncreasedValue(io);
         return result;
      }

      // add item to the end
      if (this.size == this.items.length)
         this.grow();
      this.items[this.size] = item;
      this.usage[this.size] = 1;
      this.size += 1;
      return 1;
   }

   public int get(T item)
   {
      if (item == null)
         throw new IllegalArgumentException();

      int io = this.indexOfItem(item);
      if (io == -1)
         return 0; // not -1, as the object occurred zero times
      return this.usage[io];
   }

   public List<T> topKeys()
   {
      return this.topKeys(Integer.MAX_VALUE);
   }

   public List<T> topKeys(int amount)
   {
      int end = Math.min(this.size, amount);

      // make a copy, the items are already sorted
      List<T> tops = new ArrayList<T>();
      for (int i = 0; i < end; i++)
         tops.add(this.items[i]);
      return tops;
   }

   public List<Pair<T, Integer>> topEntries()
   {
      return this.topEntries(Integer.MAX_VALUE);
   }

   public List<Pair<T, Integer>> topEntries(int amount)
   {
      int end = Math.min(this.size, amount);

      // make a copy, the items are already sorted
      List<Pair<T, Integer>> tops = new ArrayList<Pair<T, Integer>>();
      for (int i = 0; i < end; i++)
         tops.add(new Pair<T, Integer>(this.items[i], Integer.valueOf(this.usage[i])));
      return tops;
   }

   public int remove(T item)
   {
      int io = this.indexOfItem(item);
      if (io == -1)
         throw new NoSuchElementException(String.valueOf(item));

      int result = --this.usage[io];
      if (result == 0)
         return this.removeIndex(io);

      this.swapDecreasedValue(io);
      return result;
   }

   public int reset(T item)
   {
      int io = this.indexOfItem(item);
      if (io == -1)
         throw new NoSuchElementException(String.valueOf(item));
      return this.removeIndex(io);
   }

   //

   private final void swapDecreasedValue(int index)
   {
      while ((index + 1) < size && usage[index + 0] < usage[index + 1])
      {
         int a = index + 0;
         int b = index + 1;

         swapObj(items, a, b);
         swapInt(usage, a, b);

         index++;
      }
   }

   private final void swapIncreasedValue(int index)
   {
      while (index > 0 && usage[index + 0] > usage[index - 1])
      {
         int a = index - 0;
         int b = index - 1;

         swapObj(items, a, b);
         swapInt(usage, a, b);

         index--;
      }
   }

   private static final void swapInt(int[] array, int a, int b)
   {
      int temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

   private static final void swapObj(Object[] array, int a, int b)
   {
      Object temp = array[a];
      array[a] = array[b];
      array[b] = temp;
   }

   private void grow()
   {
      this.items = Arrays.copyOf(this.items, this.items.length * 2);
      this.usage = Arrays.copyOf(this.usage, this.usage.length * 2);
   }

   private int removeIndex(int index)
   {
      int count = this.usage[index];
      int shift = --this.size - index;
      System.arraycopy(this.items, index + 1, this.items, index, shift);
      System.arraycopy(this.usage, index + 1, this.usage, index, shift);
      return count;
   }

   private int indexOfItem(T item)
   {
      for (int i = 0; i < this.size; i++)
         if (this.items[i] == item || this.items[i].equals(item))
            return i;
      return -1;
   }
}

Slicing direct buffers to workaround 4K overhead

Direct ByteBuffers can have an unexpected massive overhead. For every allocation, a number of bytes equal to the system pagesize (typically 4K) is added. The reason for this is that MappedByteBuffers must be page-aligned. The code used behind the scenes in ByteBuffer.allocateDirect(int size) looks a little something like this:

private static ByteBuffer malloc(int size)
{
   int pageSize = unsafe.getPageSize(); // typically 4096
   long pointer = sun.misc.Unsafe.malloc(size + pageSize);
   long base = (pointer + (pageSize-1)) / pageSize * pageSize;
   ByteBuffer buffer = unsafe.createBufferAt(base);
   return buffer;
}

Code like this will have a massive overhead:
for(int i=0; i<count; i++)
   buffers[i] = ByteBuffer.allocateDirect(64);

Instead use an approach like below:
public class DirectBufferProvider
{
   private static final int ALLOCATION_SIZE = 1024*1024;

   private ByteBuffer currentBuffer = null;

   public ByteBuffer allocate(int size)
   {
      if(size >= ALLOCATION_SIZE)
         return ByteBuffer.allocateDirect(size);

      if(currentBuffer == null || size > currentBuffer.remaining())
         currentBuffer = ByteBuffer.allocateDirect(ALLOCATION_SIZE);

      currentBuffer.limit(currentBuffer.position() + size);
      ByteBuffer result = currentBuffer.slice();
      currentBuffer.position(currentBuffer.limit());
      currentBuffer.limit(currentBuffer.capacity());
      return result;
   }



   private static DirectBufferProvider global_synced = new DirectBufferProvider();

   public static ByteBuffer allocateDirect(int size)
   {
      synchronized(global_synced)
      {
         return global_synced.allocate(size);
      }
   }
}

Note that unlike ByteBuffer.allocateDirect(), the code in DirectBufferProvider.allocate() is not threadsafe. The static (convenience) method is synchronized and should thus not be used in heavily multithreaded code. Using ThreadLocals is even worse, performance wise, so just make new DirectBufferProvider instances when you need them.

2010-02-23

Delaying security dialogs in Java until you need them

Delaying security dialogs in Java until you need them, is a bit harder than it should be. By default, the dialog appears before the first line of code is executed, scaring off your casual visitor.

If you only occasionally need to perform actions that require elevated privileges, you can delay the security dialog to the absolute last moment (for example: right before reading/writing a file). The trick is to keep most of your code in an unsigned JAR, and the code that requires elevated privileges into a signed JAR. Use Class.forName(String) to load the signed class, which will prompt the security dialog.

Using an interface in the unsigned code, and the implementation in the signed code, you can keep your code tidy.


Note:

The browser will remember the choice of the user, until a *restart* of the browser. To workaround this (when people declined), create a dozen tiny signed JARs (with a dozen different certificates, mind you) and use a roundrobin algorithm, using serverside code or javascript that generates the applet-archive attribute. After a dozen hits and rejections, you can be sure your visitor will never grant access to his system anyway.

Update:

To make it work in MSIE, both classes MUST be in separate packages.


IMPORTANT: Since 6u19 this doesn't work anymore. You not only get a rather confusing security dialog (clicking [YES] means deny access, clicking [NO] means allow access), the two classes end up in different classloaders that cannot access eachother, resulting in ClassNotFoundException / NoClassDefFoundException. Thanks Oracle, for making Java's user experience even more secure and crap at the same time.
http://java.sun.com/javase/6/docs/technotes/guides/jweb/mixed_code.html



On to the code, which is reasonably simple.

Unsigned JAR:
package some.unsigned.stuff;

public interface SecureAccess
{
   public byte[] loadFile(File file);
   public void storeFile(File file, byte[] data);
}

     // Usage:

     File file = new File("/home/silly/image.jpg");
     Class< ? > clazz = Class.forName("some.signed.stuff.LocalSecureAccess");
     SecureAccess access = (SecureAccess) clazz.newInstance();
     byte[] data = access.loadFile(file);

Signed JAR:
package some.signed.stuff;

public class LocalSecureAccess implements SecureAccess
{
   public byte[] loadFile(final File file)
   {
      return AccessController.doPrivileged(new PrivilegedAction<byte[]>()
      {
         @Override
         public byte[] run()
         {
            return loadFileImpl(file);
         }
      });
   }

   @Override
   public void storeFile(final File file, final byte[] data)
   {
      AccessController.doPrivileged(new PrivilegedAction<Object>()
      {
         @Override
         public Object run()
         {
            storeFileImpl(file, data);

            return null;
         }
      });
   }

   // implementation

   static final int MAX_FILE_SIZE = 8 * 1024 * 1024; // prevent applet running out of memory

   byte[] loadFileImpl(File file)
   {
      DataInputStream input = null;

      try
      {
         long len = file.length();
         if (len > MAX_FILE_SIZE)
            throw new IllegalStateException("file too big: " + file);

         byte[] data = new byte[(int) len];
         input = new DataInputStream(new FileInputStream(file));
         input.readFully(data);
         input.close();
         return data;
      }
      catch (IOException exc)
      {
         throw new IllegalStateException(exc);
      }
      finally
      {
         try { if(input!=null) input.close(); } catch(IOException exc) {}
      }
   }

   void storeFileImpl(File file, byte[] data)
   {
      OutputStream output = null;

      try
      {
         output = new FileOutputStream(file);
         output.write(data);
         output.flush();
      }
      catch (IOException exc)
      {
         throw new IllegalStateException(exc);
      }
      finally
      {
         try { if(output!=null) output.close(); } catch(IOException exc) {}
      }
   }
}

Jar signing 101: (using DSA keys instead of RSA for Java 1.4 compatibility)
PATH=%PATH%;path\to\JDK\bin
SET ALIAS=MY_ALIAS
SET PASS=MY_PASSWORD
SET JAR=my.jar

keytool -delete -storepass %PASS% -alias %ALIAS%
keytool -genkey -storepass %PASS% -keypass %PASS% -keyalg DSA -alias %ALIAS%
   -dname "CN=full.domainname.com, OU=Your unit, O=Your Company,
           L=Your city, ST=Your state, C=CA,
           EMAILADDRESS=your@server.com DC=server, DC=com"
   -validity 999 (put all of this on one line)
keytool -selfcert -storepass %PASS% -alias %ALIAS% -validity 999
keytool -exportcert -storepass %PASS% -alias %ALIAS% -rfc -file %ALIAS%.cer
jarsigner -storepass %PASS% -keypass %PASS% %JAR% %ALIAS%
pause

Applet code: (nothing special)
    <applet
      code="package/of/YourApplet.class"
      archive="unsigned.jar,signed.jar"
      width="640"
      height="480">
      no applet?
    </applet>  

2010-02-04

Image :: Java Animated GIFs (with transparant pixel disposal modes)

It's a nightmare to find the code to create animated GIFs in Java. Once you found it, you notice you can't set the frame disposal, and transparent pixels will show pixels in the previous frames. The following code snippet solves this.

public class GifFrame
{
   public static final String NONE                = "none";
   public static final String DO_NOT_DISPOSE      = "doNotDispose";
   public static final String RESTORE_TO_BGCOLOR  = "restoreToBackgroundColor";
   public static final String RESTORE_TO_PREVIOUS = "restoreToPrevious";

   public final BufferedImage img;
   public final long          delay; // in millis
   public final String        disposalMethod;

   public GifFrame(BufferedImage img, long delay)
   {
      this(img, delay, NONE);
   }

   public GifFrame(BufferedImage img, long delay, String disposalMethod)
   {
      this.img = img;
      this.delay = delay;
      this.disposalMethod = disposalMethod;
   }
}

public class ImageUtil
{
   public static BufferedImage convertRGBAToGIF(BufferedImage src, int transColor)
   {
      BufferedImage dst = new BufferedImage(src.getWidth(), src.getHeight(), BufferedImage.TYPE_BYTE_INDEXED);
      Graphics g = dst.getGraphics();
      g.setColor(new Color(transColor));
      g.fillRect(0, 0, dst.getWidth(), dst.getHeight());
      {
         IndexColorModel indexedModel = (IndexColorModel) dst.getColorModel();
         WritableRaster raster = dst.getRaster();
         int sample = raster.getSample(0, 0, 0);
         int size = indexedModel.getMapSize();
         byte[] rr = new byte[size];
         byte[] gg = new byte[size];
         byte[] bb = new byte[size];
         indexedModel.getReds(rr);
         indexedModel.getGreens(gg);
         indexedModel.getBlues(bb);
         IndexColorModel newModel = new IndexColorModel(8, size, rr, gg, bb, sample);
         dst = new BufferedImage(newModel, raster, dst.isAlphaPremultiplied(), null);
      }
      dst.createGraphics().drawImage(src, 0, 0, null);
      return dst;
   }

   public static void saveAnimatedGIF(OutputStream out, List<GifFrame> frames, int loopCount) throws Exception
   {
      ImageWriter iw = ImageIO.getImageWritersByFormatName("gif").next();

      ImageOutputStream ios = ImageIO.createImageOutputStream(out);
      iw.setOutput(ios);
      iw.prepareWriteSequence(null);

      int p = 0;
      for (GifFrame frame : frames)
      {
         ImageWriteParam iwp = iw.getDefaultWriteParam();
         IIOMetadata metadata = iw.getDefaultImageMetadata(new ImageTypeSpecifier(frame.img), iwp);
         ImageUtil.configureGIFFrame(metadata, String.valueOf(frame.delay / 10L), p++, frame.disposalMethod, loopCount);
         IIOImage ii = new IIOImage(frame.img, null, metadata);
         iw.writeToSequence(ii, null);
      }

      iw.endWriteSequence();
      ios.close();
   }

   private static void configureGIFFrame(IIOMetadata meta, String delayTime, int imageIndex, String disposalMethod, int loopCount)
   {
      String metaFormat = meta.getNativeMetadataFormatName();

      if (!"javax_imageio_gif_image_1.0".equals(metaFormat))
      {
         throw new IllegalArgumentException("Unfamiliar gif metadata format: " + metaFormat);
      }

      Node root = meta.getAsTree(metaFormat);

      Node child = root.getFirstChild();
      while (child != null)
      {
         if ("GraphicControlExtension".equals(child.getNodeName()))
            break;
         child = child.getNextSibling();
      }

      IIOMetadataNode gce = (IIOMetadataNode) child;
      gce.setAttribute("userDelay", "FALSE");
      gce.setAttribute("delayTime", delayTime);
      gce.setAttribute("disposalMethod", disposalMethod);

      if (imageIndex == 0)
      {
         IIOMetadataNode aes = new IIOMetadataNode("ApplicationExtensions");
         IIOMetadataNode ae = new IIOMetadataNode("ApplicationExtension");
         ae.setAttribute("applicationID", "NETSCAPE");
         ae.setAttribute("authenticationCode", "2.0");
         byte[] uo = new byte[] { 0x1, (byte) (loopCount & 0xFF), (byte) ((loopCount >> 8) & 0xFF) };
         ae.setUserObject(uo);
         aes.appendChild(ae);
         root.appendChild(aes);
      }

      try
      {
         meta.setFromTree(metaFormat, root);
      }
      catch (IIOInvalidTreeException e)
      {
         throw new Error(e);
      }
   }
}

Usage:
List<GifFrame> gifFrames = new ArrayList<GifFrame>();

   for(BufferedImage image: images)
   {
      int transparantColor = 0xFF00FF; // purple
      BufferedImage gif = convertRGBAToGIF(image, transparantColor);
      long delay = 100; // every frame takes 100ms
      String disposal = GifFrame.RESTORE_TO_BGCOLOR; // make transparent pixels not 'shine through'
      gifFrames.add(new GifFrame(gif, delay, disposal));
   }

   int loopCount = 0; // loop indefinitely
   saveAnimatedGIF(outputStream, gifFrames, loopCount);

Image :: read/write TGA

public static BufferedImage readTGA(File file) throws IOException
   {
      if (!file.exists())
         throw new FileNotFoundException(file.getAbsolutePath());

      byte[] header = new byte[18];
      int len = (int) file.length() - header.length;
      if (len < 0)
         throw new IllegalStateException("file not big enough to contain header: " + file.getAbsolutePath());
      byte[] data = new byte[len];

      RandomAccessFile raf = new RandomAccessFile(file, "r");
      raf.read(header);
      raf.read(data);
      raf.close();

      if ((header[0] | header[1]) != 0)
         throw new IllegalStateException(file.getAbsolutePath());
      if (header[2] != 2)
         throw new IllegalStateException(file.getAbsolutePath());
      int w = 0, h = 0;
      w |= (header[12] & 0xFF) << 0;
      w |= (header[13] & 0xFF) << 8;
      h |= (header[14] & 0xFF) << 0;
      h |= (header[15] & 0xFF) << 8;

      boolean alpha;
      if ((w * h) * 3 == data.length)
         alpha = false;
      else if ((w * h) * 4 == data.length)
         alpha = true;
      else
         throw new IllegalStateException(file.getAbsolutePath());
      if (!alpha && (header[16] != 24))
         throw new IllegalStateException(file.getAbsolutePath());
      if (alpha && (header[16] != 32))
         throw new IllegalStateException(file.getAbsolutePath());
      if ((header[17] & 15) != (alpha ? 8 : 0))
         throw new IllegalStateException(file.getAbsolutePath());

      BufferedImage dst = new BufferedImage(w, h, alpha ? BufferedImage.TYPE_INT_ARGB : BufferedImage.TYPE_INT_RGB);
      int[] pixels = ((DataBufferInt) dst.getRaster().getDataBuffer()).getData();
      if (pixels.length != w * h)
         throw new IllegalStateException(file.getAbsolutePath());
      if (data.length != pixels.length * (alpha ? 4 : 3))
         throw new IllegalStateException(file.getAbsolutePath());

      if (alpha)
      {
         for (int i = 0, p = (pixels.length - 1) * 4; i < pixels.length; i++, p -= 4)
         {
            pixels[i] |= ((data[p + 0]) & 0xFF) << 0;
            pixels[i] |= ((data[p + 1]) & 0xFF) << 8;
            pixels[i] |= ((data[p + 2]) & 0xFF) << 16;
            pixels[i] |= ((data[p + 3]) & 0xFF) << 24;
         }
      }
      else
      {
         for (int i = 0, p = (pixels.length - 1) * 3; i < pixels.length; i++, p -= 3)
         {
            pixels[i] |= ((data[p + 0]) & 0xFF) << 0;
            pixels[i] |= ((data[p + 1]) & 0xFF) << 8;
            pixels[i] |= ((data[p + 2]) & 0xFF) << 16;
         }
      }

      if ((header[17] >> 4) == 1)
      {
         // ok
      }
      else if ((header[17] >> 4) == 0)
      {
         // flip horizontally

         for (int y = 0; y < h; y++)
         {
            int w2 = w / 2;
            for (int x = 0; x < w2; x++)
            {
               int a = (y * w) + x;
               int b = (y * w) + (w - 1 - x);
               int t = pixels[a];
               pixels[a] = pixels[b];
               pixels[b] = t;
            }
         }
      }
      else
      {
         throw new UnsupportedOperationException(file.getAbsolutePath());
      }

      return dst;
   }

   public static void writeTGA(BufferedImage src, File file) throws IOException
   {
      DataBuffer buffer = src.getRaster().getDataBuffer();
      boolean alpha = src.getColorModel().hasAlpha();
      byte[] data;

      if (buffer instanceof DataBufferByte)
      {
         byte[] pixels = ((DataBufferByte) src.getRaster().getDataBuffer()).getData();
         if (pixels.length != src.getWidth() * src.getHeight() * (alpha ? 4 : 3))
            throw new IllegalStateException();

         data = new byte[pixels.length];

         for (int i = 0, p = pixels.length - 1; i < data.length; i++, p--)
         {
            data[i] = pixels[p];
         }
      }
      else if (buffer instanceof DataBufferInt)
      {
         int[] pixels = ((DataBufferInt) src.getRaster().getDataBuffer()).getData();
         if (pixels.length != src.getWidth() * src.getHeight())
            throw new IllegalStateException();

         data = new byte[pixels.length * (alpha ? 4 : 3)];

         if (alpha)
         {
            for (int i = 0, p = pixels.length - 1; i < data.length; i += 4, p--)
            {
               data[i + 0] = (byte) ((pixels[p] >> 0) & 0xFF);
               data[i + 1] = (byte) ((pixels[p] >> 8) & 0xFF);
               data[i + 2] = (byte) ((pixels[p] >> 16) & 0xFF);
               data[i + 3] = (byte) ((pixels[p] >> 24) & 0xFF);
            }
         }
         else
         {
            for (int i = 0, p = pixels.length - 1; i < data.length; i += 3, p--)
            {
               data[i + 0] = (byte) ((pixels[p] >> 0) & 0xFF);
               data[i + 1] = (byte) ((pixels[p] >> 8) & 0xFF);
               data[i + 2] = (byte) ((pixels[p] >> 16) & 0xFF);
            }
         }
      }
      else
      {
         throw new UnsupportedOperationException();
      }

      byte[] header = new byte[18];
      header[2] = 2; // uncompressed, true-color image
      header[12] = (byte) ((src.getWidth() >> 0) & 0xFF);
      header[13] = (byte) ((src.getWidth() >> 8) & 0xFF);
      header[14] = (byte) ((src.getHeight() >> 0) & 0xFF);
      header[15] = (byte) ((src.getHeight() >> 8) & 0xFF);
      header[16] = (byte) (alpha ? 32 : 24); // bits per pixel
      header[17] = (byte) ((alpha ? 8 : 0) | (1 << 4));

      RandomAccessFile raf = new RandomAccessFile(file, "rw");
      raf.write(header);
      raf.write(data);
      raf.setLength(raf.getFilePointer()); // trim
      raf.close();
   }

FastMath :: fast floor + ceil

Calling Math.floor() simply takes too long. The problem with optimizing is that you can't simply cast the floatingpoint number to an integer, because that will result in invalid results for negative numbers. If we know our input values are in a specific range, we can safely add a certain (big) constant to the input, cast the guaranteed positive value to an integer and subtract the constant again.

The code is ~9x faster than Math.floor(). Replacing the doubles with floats makes it faster, but the results are rather... random, so don't.

public class FastMath
{
   private static final int    BIG_ENOUGH_INT   = 16 * 1024;
   private static final double BIG_ENOUGH_FLOOR = BIG_ENOUGH_INT + 0.0000;
   private static final double BIG_ENOUGH_ROUND = BIG_ENOUGH_INT + 0.5000;
   private static final double BIG_ENOUGH_CEIL  = BIG_ENOUGH_INT + 0.9999;

   public static int fastFloor(float x) {
      return (int) (x + BIG_ENOUGH_FLOOR) - BIG_ENOUGH_INT;
   }

   public static int fastRound(float x) {
      return (int) (x + BIG_ENOUGH_ROUND) - BIG_ENOUGH_INT;
   }

   public static int fastCeil(float x) {
      return (int) (x + BIG_ENOUGH_CEIL) - BIG_ENOUGH_INT;
   }
}

2009-10-26

Image :: read size of JPG/PNG/BMP/GIF

If you would believe Google, everybody is searching for code that reads the dimensions of an image,without loading all those colorful pixels. Oh well, without further ado....

public class ImageUtil
{
   public static Dimension getImageDimension(File file) throws IOException
   {
      return ImageUtil.getImageDimension(new FileInputStream(file));
   }

   public static Dimension getImageDimension(InputStream in) throws IOException
   {
      DataInputStream dis = new DataInputStream(in);

      try
      {
         int header = dis.readUnsignedShort();

         if (header == 0x8950)
         {
            // PNG
            dis.readFully(new byte[(8 - 2) + 4 + 4]); // thanks Abuse

            return new Dimension(dis.readInt(), dis.readInt());
         }

         if (header == 0xffd8)
         {
            // JPG (see below)
         }
         else if (header == 0x424D)
         {
            // BMP
            dis.readFully(new byte[16]);

            int w = dis.read() | (dis.read() << 8) | (dis.read() << 16) | (dis.read() << 24);
            int h = dis.read() | (dis.read() << 8) | (dis.read() << 16) | (dis.read() << 24);
            return new Dimension(w, h);
         }
         else if (header == (('G' << 8) | ('I' << 0))) // GIF
         {
            // GIF
            dis.readFully(new byte[4]);
            int w = dis.read() | (dis.read() << 8);
            int h = dis.read() | (dis.read() << 8);
            return new Dimension(w, h);
         }
         else
         {
            throw new IllegalStateException("unexpected header: " + Integer.toHexString(header));
         }

         while (true) // JPG is not so straight forward
         {
            int marker = dis.readUnsignedShort();

            switch (marker)
            {
               case 0xffd8: // SOI
               case 0xffd0: // RST0
               case 0xffd1: // RST1
               case 0xffd2: // RST2
               case 0xffd3: // RST3
               case 0xffd4: // RST4
               case 0xffd5: // RST5
               case 0xffd6: // RST6
               case 0xffd7: // RST7
               case 0xffd9: // EOI
                  break;

               case 0xffdd: // DRI
                  dis.readUnsignedShort();
                  break;

               case 0xffe0: // APP0
               case 0xffe1: // APP1
               case 0xffe2: // APP2
               case 0xffe3: // APP3
               case 0xffe4: // APP4
               case 0xffe5: // APP5
               case 0xffe6: // APP6
               case 0xffe7: // APP7
               case 0xffe8: // APP8
               case 0xffe9: // APP9
               case 0xffea: // APPa
               case 0xffeb: // APPb
               case 0xffec: // APPc
               case 0xffed: // APPd
               case 0xffee: // APPe
               case 0xffef: // APPf
               case 0xfffe: // COM
               case 0xffdb: // DQT
               case 0xffc4: // DHT
               case 0xffda: // SOS
                  dis.readFully(new byte[dis.readUnsignedShort() - 2]);
                  break;

               case 0xffc0: // SOF0
               case 0xffc2: // SOF2
                  dis.readUnsignedShort();
                  dis.readByte();
                  int height = dis.readUnsignedShort();
                  int width = dis.readUnsignedShort();
                  return new Dimension(width, height);

               default:
                  throw new IllegalStateException("invalid jpg marker: " + Integer.toHexString(marker));
            }
         }
      }
      finally
      {
         dis.close();
      }
   }
}

2009-08-30

Graycode :: for analog stuff!

THIS WAS FUN.

Proved the math teacher wrong.

public class Graycode
{
   public static int normalToGray(int orig)
   {
      int gray = 0;
      for (int n = 0; n < 31; n++)
         gray |= (((orig + (1 << n)) >> (n + 1)) & 1) << n;
      return gray;
   }

   public static int grayToNormal(int gray)
   {
      int parity = 0;
      int norm = 0;
      for (int pos = 31; pos >= 0; pos--)
         norm = (norm << 1) | (parity ^= ((gray >> pos) & 1));
      return norm;
   }

   public static int changedBitInNextGrayCode(int gray)
   {
      for (int i = 0; i < 31; i++)
         if (parity(gray >> i) == 0)
            return i + 1;
      return -1;
   }

   private static int parity(int v)
   {
      int c = 0;
      for (int i = 0; i < 31; i++)
         c ^= (v & (1 << i)) >> i;
      return c;
   }
}

Set :: binary operations

Everybody should have these. It's just a drag to rewrite it time and time again.

public class SetUtil
{
   public static <T> Set<T> and(Set<T> a, Set<T> b)
   {
      Set<T> c = new HashSet<T>();
      // c.addAll(SetUtil.or(a, b));
      // c.removeAll(SetUtil.xor(a, b));
      c.addAll(a);
      c.retainAll(b);
      return c;
   }

   public static <T> Set<T> or(Set<T> a, Set<T> b)
   {
      Set<T> c = new HashSet<T>();
      c.addAll(a);
      c.addAll(b);
      return c;
   }

   public static <T> Set<T> xor(Set<T> a, Set<T> b)
   {
      Set<T> a_minus_b = new HashSet<T>();
      a_minus_b.addAll(a);
      a_minus_b.removeAll(b);

      Set<T> b_minus_a = new HashSet<T>();
      b_minus_a.addAll(b);
      b_minus_a.removeAll(a);

      Set<T> c = new HashSet<T>();
      c.addAll(a_minus_b);
      c.addAll(b_minus_a);
      return c;
   }
}

ArraySorter :: in-place, pre-calc

The point of this class is to pre-calculate the sort-order in advance, so that we're not comparing objects all the time, and then do a proper/fast sort. In-place, meaning not creating an auxillary array, like Arrays.sort() does. This class is thread safe, as in... synchronized.

The 'chunked' version uses 'bucket sort' and then does a regular sort on the buckets, and merges the result back in the original array.

The Sortable interface is expected to calculate the sort-index in calcSortIndex() and return that value each and every time in getSortIndex()


public interface Sortable
{
   public void calcSortIndex();

   public int getSortIndex();
}

public class ArraySorter
{
   public static final synchronized void fineSort(Sortable[] p, int off, int len)
   {
      for (int i = 0; i < len; i++)
         p[off + i].calcSortIndex();

      ArraySorter.doFineSortImpl(p, off, len);
   }

   public static final synchronized void chunkedSort(Sortable[] p, int off, int len, int min, int max, int chunks)
   {
      for (int i = 0; i < len; i++)
         p[off + i].calcSortIndex();

      ArraySorter.doChunkedSortImpl(p, off, len, min, max, chunks);
   }

   /**
    * FINE
    */

   private static final void doFineSortImpl(Sortable[] p, int off, int len)
   {
      if (len < 7)
      {
         for (int i = off; i < len + off; i++)
            for (int j = i; j > off && p[j - 1].getSortIndex() > p[j].getSortIndex(); j--)
               swap(p, j, j - 1);

         return;
      }

      int m = off + (len >> 1);

      if (len > 7)
      {
         int l = off;
         int n = off + len - 1;

         if (len > 40)
         {
            int s = len >>> 3;
            l = med3(p, l, l + s, l + 2 * s);
            m = med3(p, m - s, m, m + s);
            n = med3(p, n - 2 * s, n - s, n);
         }

         m = med3(p, l, m, n);
      }

      int v = p[m].getSortIndex();

      int a = off;
      int b = a;
      int c = off + len - 1;
      int d = c;

      while (true)
      {
         while (b <= c && p[b].getSortIndex() <= v)
         {
            if (p[b].getSortIndex() == v)
               swap(p, a++, b);
            b++;
         }

         while (c >= b && p[c].getSortIndex() >= v)
         {
            if (p[c].getSortIndex() == v)
               swap(p, c, d--);
            c--;
         }

         if (b > c)
            break;

         swap(p, b++, c--);
      }

      int s, n = off + len;
      s = Math.min(a - off, b - a);
      swapRange(p, off, b - s, s);
      s = Math.min(d - c, n - d - 1);
      swapRange(p, b, n - s, s);

      if ((s = b - a) > 1)
         doFineSortImpl(p, off, s);

      if ((s = d - c) > 1)
         doFineSortImpl(p, n - s, s);
   }

   private static final void swap(Sortable[] p, int a, int b)
   {
      Sortable q = p[a];
      p[a] = p[b];
      p[b] = q;
   }

   private static final void swapRange(Sortable[] p, int a, int b, int n)
   {
      Sortable q;

      for (int i = 0; i < n; i++, a++, b++)
      {
         q = p[a];
         p[a] = p[b];
         p[b] = q;
      }
   }

   private static final int med3(Sortable[] p, int a, int b, int c)
   {
      int a0 = p[a].getSortIndex();
      int b0 = p[b].getSortIndex();
      int c0 = p[c].getSortIndex();
      return (a0 < b0 ? (b0 < c0 ? b : (a0 < c0 ? c : a)) : (b0 > c0 ? b : (a0 > c0 ? c : a)));
   }

   /**
    * CHUNKED
    */

   private static List<Sortable>   less  = new ArrayList<Sortable>();
   private static List<Sortable>[] parts = new List[0];
   private static List<Sortable>   more  = new ArrayList<Sortable>();
   private static Sortable[]       tmp   = new Sortable[64];

   private static final void doChunkedSortImpl(Sortable[] p, int off, int len, int min, int max, int chunks)
   {
      if (parts.length < chunks)
      {
         parts = new List[chunks];

         for (int i = 0; i < parts.length; i++)
            parts[i] = new ArrayList<Sortable>();
      }

      // sort-index is already calculated here

      // distribute sortables over lists
      for (int i = 0; i < len; i++)
      {
         Sortable s = p[off + i];
         int index = s.getSortIndex();

         if (index < min)
            less.add(s);
         else if (index >= max)
            more.add(s);
         else
         {
            float percent = (float) (s.getSortIndex() - min) / (max - min);
            int arrayIndex = (int) (percent * chunks);
            parts[arrayIndex].add(s);
         }
      }

      // sort lists, overwrite P
      tmp = less.toArray(tmp);
      ArraySorter.doFineSortImpl(tmp, 0, less.size());
      System.arraycopy(tmp, 0, p, off, less.size());
      off += less.size();

      for (int i = 0; i < chunks; i++)
      {
         if (parts[i].isEmpty())
            continue;

         tmp = parts[i].toArray(tmp);
         ArraySorter.doFineSortImpl(tmp, 0, parts[i].size());
         System.arraycopy(tmp, 0, p, off, parts[i].size());
         off += parts[i].size();
      }

      tmp = more.toArray(tmp);
      ArraySorter.doFineSortImpl(tmp, 0, more.size());
      System.arraycopy(tmp, 0, p, off, more.size());
      off += more.size();

      // clear up all references
      less.clear();
      for (int i = 0; i < chunks; i++)
         parts[i].clear();
      more.clear();
   }
}

Histogram :: map-based

public class Histogram<T>
{
   private final Map<T, Integer> map;

   public Histogram()
   {
      this.map = new HashMap<T, Integer>();
   }

   public int put(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         count = Integer.valueOf(0);
      count = Integer.valueOf(count.intValue() + 1);
      this.map.put(t, count);
      return count.intValue();
   }

   public int get(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         return 0;
      return count.intValue();
   }

   public List<T> topKeys(int amount)
   {
      //int threshold = Integer.MIN_VALUE;

      List<T> kList = new ArrayList<T>();
      List vList = new ArrayList();

      for (Entry e : this.map.entrySet())
      {
         //int val = e.getValue().intValue();
         //if (val <= threshold)
         {
            //continue;
         }

         // when full, remove lowest
         if (vList.size() == amount)
         {
            int index = indexOfMin(vList);
            kList.remove(index);
            vList.remove(index);
         }

         kList.add(e.getKey());
         vList.add(e.getValue());
      }

      // bubble sort
      for (int i = 0; i < vList.size(); i++)
      {
         for (int k = i + 1; k < vList.size(); k++)
         {
            if (vList.get(i).intValue() >= vList.get(k).intValue())
            {
               continue;
            }

            Integer a = vList.get(i);
            Integer b = vList.get(k);
            vList.set(k, a);
            vList.set(i, b);

            T x = kList.get(i);
            T y = kList.get(k);
            kList.set(k, x);
            kList.set(i, y);
         }
      }

      return kList;
   }

   public int remove(T t)
   {
      Integer count = this.map.get(t);
      if (count == null)
         throw new NoSuchElementException(String.valueOf(t));
      if (count.intValue() == 0)
         throw new IllegalStateException("cannot remove");

      count = Integer.valueOf(count.intValue() - 1);
      if (count.intValue() == 0)
         this.map.remove(t);
      else
         this.map.put(t, count);

      return count.intValue();
   }

   public int reset(T t)
   {
      Integer count = this.map.remove(t);
      if (count == null)
         return 0;
      return count.intValue();
   }

   public int set(T t, int val)
   {
      if (val < 0)
         throw new IllegalArgumentException();
      Integer count = this.map.get(t);

      if (count == null)
      {
         if (val != 0)
            this.map.put(t, Integer.valueOf(val));
         return 0;
      }

      if (val == 0)
         return this.map.remove(t).intValue();
      return this.map.put(t, Integer.valueOf(val)).intValue();
   }

   public Set<T> keys()
   {
      return this.map.keySet();
   }

   private static int indexOfMin(List<Integer> ids)
   {
      int minAt = 0;
      for (int i = 1; i < ids.size(); i++)
         if (ids.get(i).intValue() < ids.get(minAt).intValue())
            minAt = i;
      return minAt;
   }
}

Unsafe :: Pointers

   private final static Unsafe   unsafe;
   private static long           addressOffset;
   private static long           positionOffset;
   private static long           limitOffset;
   private static long           capacityOffset;

   public static final long      WORD_SIZE_BITS, HEADER_SIZE;
   public static final long      BYTE_ARRAY_BASE_OFFSET;
   public static final long      SHORT_ARRAY_BASE_OFFSET;
   public static final long      INT_ARRAY_BASE_OFFSET;
   public static final long      LONG_ARRAY_BASE_OFFSET;
   public static final long      FLOAT_ARRAY_BASE_OFFSET;
   public static final long      DOUBLE_ARRAY_BASE_OFFSET;
   public static final long      OBJECT_ARRAY_BASE_OFFSET;
   private static final Object[] holder = new Object[1];

   static
   {
      try
      {
         ByteBuffer buffer = ByteBuffer.allocateDirect(1);
         Field unsafeField = buffer.getClass().getDeclaredField("unsafe");
         unsafeField.setAccessible(true);
         unsafe = (Unsafe) unsafeField.get(buffer);
         unsafeField.setAccessible(false);

         addressOffset = getObjectFieldOffset(buffer, "address");
         positionOffset = getObjectFieldOffset(buffer, "position");
         limitOffset = getObjectFieldOffset(buffer, "limit");
         capacityOffset = getObjectFieldOffset(buffer, "capacity");

         buffer.flip();
         buffer = null;
      }
      catch (Exception exc)
      {
         exc.printStackTrace();
         throw new InternalError();
      }

      WORD_SIZE_BITS = unsafe.addressSize() * 8;
      if (WORD_SIZE_BITS != 32 && WORD_SIZE_BITS != 64)
         throw new IllegalStateException("WORD_SIZE: " + WORD_SIZE_BITS);
      HEADER_SIZE = WORD_SIZE_BITS / 8 * 2;

      BYTE_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new byte[4].getClass());
      SHORT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new short[4].getClass());
      INT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new int[4].getClass());
      LONG_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new long[4].getClass());
      FLOAT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new float[4].getClass());
      DOUBLE_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new double[4].getClass());
      OBJECT_ARRAY_BASE_OFFSET = unsafe.arrayBaseOffset(new Object[4].getClass());
   }

   public static final long getObjectAddress(Object obj)
   {
      holder[0] = obj;

      if (WORD_SIZE_BITS == 32)
         return unsafe.getInt(holder, OBJECT_ARRAY_BASE_OFFSET);
      if (WORD_SIZE_BITS == 64)
         return unsafe.getLong(holder, OBJECT_ARRAY_BASE_OFFSET);

      throw new IllegalStateException();
   }

   public static final Object getObjectAtAddress(long addr)
   {
      if (WORD_SIZE_BITS == 32)
         unsafe.putInt(holder, OBJECT_ARRAY_BASE_OFFSET, (int) (addr & 0xFFFFFFFF));
      if (WORD_SIZE_BITS == 64)
         unsafe.putLong(holder, OBJECT_ARRAY_BASE_OFFSET, addr);

      return holder[0];
   }

   public static final FloatBuffer createFloatBufferAt(long pntr, int len)
   {
      Native.zeroOut(pntr, len << 2);

      FloatBuffer buf = ByteBuffer.allocateDirect(4).order(ByteOrder.nativeOrder()).asFloatBuffer();
      NativeHacks.setBufferProperties(buf, pntr, 0, len, len);
      buf.clear();

      return buf;
   }

   public static final float[] createFloatArrayAt(long pntr, int len)
   {
      NativeHacks.copyObjectHeaderTo(new float[0], pntr);

      // write length
      unsafe.putInt(pntr + HEADER_SIZE, len);

      return (float[]) NativeHacks.fakePointerAsObject(pntr);
   }

   public static final void copyObjectHeaderTo(Object obj, long pntr)
   {
      for (int i = 0; i < HEADER_SIZE; i++)
         unsafe.putByte(pntr + i, unsafe.getByte(obj, (long) i));
   }

   public static final Object fakePointerAsObject(long addr)
   {
      if (WORD_SIZE_BITS == 32)
         unsafe.putInt(holder, OBJECT_ARRAY_BASE_OFFSET, (int) (addr & 0xFFFFFFFF));
      else if (WORD_SIZE_BITS == 64)
         unsafe.putLong(holder, OBJECT_ARRAY_BASE_OFFSET, addr);
      else
         throw new IllegalStateException();

      return holder[0];
   }

2009-08-25

Thread :: monitor CPU usage

If you want to monitor CPU usage, per thread, things couldn't get easier!

ThreadGroupMonitor gmonitor = new ThreadGroupMonitor();

while(true)
{
   gmonitor.poll();

   for(ThreadMonitor tmon: gmonitor.getAliveThreadMonitors())
   {
      double avg = tmon.getCpuTimeStats().avg();  // avg of last polls
      double avg = tmon.getCpuTimeStats().avg(3); // avg of last 3 polls
      double avg = tmon.getCpuTimeStats().avg(5); // avg of last 5 polls
   }

   for(ThreadMonitor tmon: gmonitor.getDeadThreadMonitors())
   {
      double total = tmon.getTotalCpuTime();
   }

   // sleep for a bit
}

Even dead threads...

public class ThreadMonitor
{
   private static ThreadMXBean tmxb;

   static
   {
      tmxb = ManagementFactory.getThreadMXBean();
      tmxb.setThreadCpuTimeEnabled(true);
   }

   //

   private long                tid;
   private CyclicUsageHistory  cpuTimeHistory;
   private CyclicUsageHistory  userTimeHistory;
   private CyclicUsageHistory  cpuUsageHistory;
   private CyclicUsageHistory  userUsageHistory;

   public ThreadMonitor(long tid, int slots)
   {
      this.tid = tid;
      this.cpuTimeHistory = new CyclicUsageHistory(slots);
      this.userTimeHistory = new CyclicUsageHistory(slots);
      this.cpuUsageHistory = new CyclicUsageHistory(slots);
      this.userUsageHistory = new CyclicUsageHistory(slots);
   }

   public long getId()
   {
      return tid;
   }

   private double totalCpuTime;
   private double totalUserTime;
   
   public double getTotalCpuTime()
   {
      return this.totalCpuTime;
   }
   
   public double getTotalUserTime()
   {
      return this.totalUserTime;
   }

   public void poll()
   {
      // a time of -1 means not alive

      double cpuTime = tmxb.getThreadCpuTime(this.tid) / 1000000000.0;
      this.totalCpuTime += cpuTime < 0 ? 0 : cpuTime;
      cpuTimeHistory.log(cpuTime < 0 ? 0 : cpuTime);
      cpuUsageHistory.log(cpuTimeHistory.previous(0) - cpuTimeHistory.previous(1));

      double userTime = tmxb.getThreadUserTime(this.tid) / 1000000000.0;
      this.totalUserTime += userTime < 0 ? 0 : userTime;
      userTimeHistory.log(userTime < 0 ? 0 : userTime);
      userUsageHistory.log(userTimeHistory.previous(0) - userTimeHistory.previous(1));
   }

   public CyclicUsageHistory getCpuTimeStats()
   {
      return this.cpuUsageHistory;
   }

   public CyclicUsageHistory getUserTimeStats()
   {
      return this.userUsageHistory;
   }
}

public class ThreadGroupMonitor
{
   public ThreadGroupMonitor()
   {
      this(Thread.currentThread().getThreadGroup());
   }

   public ThreadGroupMonitor(ThreadGroup group)
   {
      this.group = group;
      this.lastThreadIds = new long[0];
      this.aliveId2mon = new HashMap();
      this.deadId2mon = new HashMap();
   }

   //

   private final ThreadGroup group;

   public ThreadGroup getThreadGroup()
   {
      return group;
   }

   //

   private int totalDeadThreadCount = 0;

   public synchronized int getTotalDeadThreadCount()
   {
      return this.totalDeadThreadCount;
   }

   //

   private int regularThreadCount = 0;

   public synchronized int getRegularThreadCount()
   {
      return this.regularThreadCount;
   }

   //

   private int deamonThreadCount = 0;

   public synchronized int getDeamonThreadCount()
   {
      return this.deamonThreadCount;
   }

   //

   private static final int         default_slots = 3600;

   private long[]                   lastThreadIds;
   private Map aliveId2mon;
   private Map deadId2mon;

   public synchronized void poll()
   {
      Thread[] threads = this.findAllThreads();

      long[] currThreadIds = this.findAllThreadIds(threads);
      long[] newIds = this.findNewThreadIds(this.lastThreadIds, currThreadIds);
      long[] deadIds = this.findDeadThreadIds(this.lastThreadIds, currThreadIds);

      this.totalDeadThreadCount += deadIds.length;

      for (long newId : newIds)
         aliveId2mon.put(Long.valueOf(newId), new ThreadMonitor(newId, default_slots));
      for (long deadId : deadIds)
         deadId2mon.put(Long.valueOf(deadId), aliveId2mon.remove(Long.valueOf(deadId)));

      for (ThreadMonitor mon : aliveId2mon.values())
         mon.poll();
      for (ThreadMonitor mon : deadId2mon.values())
         mon.poll();

      this.analyzeThreads(threads);

      this.lastThreadIds = currThreadIds;
   }

   public synchronized double getAvgCpuTimeStats(int pollCount)
   {
      double sum = 0.0;
      for (ThreadMonitor mon : aliveId2mon.values())
         sum += mon.getCpuTimeStats().avg(pollCount);
      return sum;
   }

   public synchronized double getAvgUserTimeStats(int pollCount)
   {
      double sum = 0.0;
      for (ThreadMonitor mon : aliveId2mon.values())
         sum += mon.getUserTimeStats().avg(pollCount);
      return sum;
   }

   public Collection getAliveThreadMonitors()
   {
      return Collections.unmodifiableCollection(this.aliveId2mon.values());
   }

   public Collection getDeadThreadMonitors()
   {
      return Collections.unmodifiableCollection(this.deadId2mon.values());
   }

   private void analyzeThreads(Thread[] threads)
   {
      int deamonThreadCount = 0;
      int regularThreadCount = 0;

      for (Thread thread : threads)
      {
         if (!thread.isAlive())
            continue;
         if (thread.isDaemon())
            deamonThreadCount++;
         else
            regularThreadCount++;
      }

      this.deamonThreadCount = deamonThreadCount;
      this.regularThreadCount = regularThreadCount;
   }

   public Thread[] findAllThreads()
   {
      int threadCount;

      Thread[] tempThreadArray = new Thread[8];
      while ((threadCount = this.group.enumerate(tempThreadArray)) == tempThreadArray.length)
         tempThreadArray = ArrayUtil.growTo(tempThreadArray, tempThreadArray.length * 2);

      Thread[] threadArray = new Thread[threadCount];
      System.arraycopy(tempThreadArray, 0, threadArray, 0, threadCount);
      return threadArray;
   }

   private long[] findAllThreadIds(Thread[] threads)
   {
      long[] allThreadIds = new long[threads.length];
      for (int i = 0; i < allThreadIds.length; i++)
         allThreadIds[i] = threads[i].getId();
      return allThreadIds;
   }

   private long[] findNewThreadIds(long[] lastThreads, long[] currThreads)
   {
      long[] newThreadIds = new long[currThreads.length];
      int newThreadIndex = 0;

      outer: for (int i = 0; i < currThreads.length; i++)
      {
         for (int k = 0; k < lastThreads.length; k++)
            if (currThreads[i] == lastThreads[k])
               continue outer;
         newThreadIds[newThreadIndex++] = currThreads[i];
      }

      long[] ids = new long[newThreadIndex];
      System.arraycopy(newThreadIds, 0, ids, 0, newThreadIndex);
      return ids;
   }

   private long[] findDeadThreadIds(long[] lastThreads, long[] currThreads)
   {
      long[] deadThreadIds = new long[lastThreads.length];
      int deadThreadIndex = 0;

      outer: for (int i = 0; i < lastThreads.length; i++)
      {
         for (int k = 0; k < currThreads.length; k++)
            if (lastThreads[i] == currThreads[k])
               continue outer;
         deadThreadIds[deadThreadIndex++] = lastThreads[i];
      }

      long[] ids = new long[deadThreadIndex];
      System.arraycopy(deadThreadIds, 0, ids, 0, deadThreadIndex);
      return ids;
   }
}

public class CyclicUsageHistory
{
   private final double[] values;

   public CyclicUsageHistory(int slots)
   {
      this.values = new double[slots];
   }

   private int addIndex;

   public void log(double value)
   {
      this.values[this.addIndex++ % this.values.length] = value;
   }
   
   //

   public double previous()
   {
      return this.previous(0);
   }

   public double previous(int age)
   {
      int len = this.values.length;
      return this.values[(((this.addIndex - 1 - age) % len) + len) % len];
   }

   //

   public double max()
   {
      return this.max(this.values.length);
   }

   public double max(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));

      double max = 0.0;
      for (int i = 0; i < count; i++)
         if (this.previous(i) > max)
            max = this.previous(i);
      return max;
   }

   //

   public double sum()
   {
      return this.sum(this.values.length);
   }

   public double sum(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));

      double sum = 0.0;
      for (int i = 0; i < count; i++)
         sum += this.previous(i);
      return sum;
   }

   //

   public double avg()
   {
      return this.avg(this.values.length);
   }

   public double avg(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));

      return this.sum(slots) / count;
   }

   //

   public double nom()
   {
      return this.nom(this.values.length);
   }

   public double nom(int slots)
   {
      int count = Math.min(this.values.length, Math.min(slots, this.addIndex - 1));
      if (count == 0)
         return 0.0;

      double[] arr = new double[count];
      for (int i = 0; i < count; i++)
         arr[i] = this.previous(i);
      Arrays.sort(arr);
      return arr[arr.length / 2];
   }
}

Swappable Jar ClassLoader

So you have this pluggable stuff, and you want to support realtime loading of new classes. That's not so hard, but what if old classes try to load old classes, and the JAR has been replaced? Right! Native crash. Blehh.

With DynamicJarClassLoader you can do this:
ClassLoader loader = new DynamicJarClassLoader(parent, file);
Class clzz1 = loader.loadClass("my.package.MyClass");
// ...
// JAR is replaced
// ...
Class clzz2 = loader.loadClass("my.package.MyClass");
// ...
clzz1.newInstance(); // loads old "other.package.OtherClass"
clzz2.newInstance(); // loads new "other.package.OtherClass"

Let's say MyClass will also load "other.package.OtherClass" sooner or later. The classloader will keep that data loaded, so that clzz1 and clzz2 have access to their own version of OtherClass.

Fancy stuff!

public class DynamicJarClassLoader extends DynamicClassLoader
{
   private final File        jar;
   private long              prevLastModified;
   private final Set resourceNames;

   public DynamicJarClassLoader(ClassLoader parent, File jar)
   {
      super(parent);

      this.jar = jar;
      this.prevLastModified = -1L;
      this.resourceNames = new HashSet();

      this.ensureLatestClassLoader();
   }

   public File getJar()
   {
      return this.jar;
   }

   public Set getResourceNames()
   {
      return Collections.unmodifiableSet(this.resourceNames);
   }

   private static final long file_idle_timeout = 3 * 1000;

   @Override
   public boolean isUpdated()
   {
      long jarLastModified = this.jar.lastModified();

      boolean willBeUpdated = jarLastModified != this.prevLastModified;

      if (willBeUpdated && this.prevLastModified != -1L)
      {
         if (this.jar.lastModified() > System.currentTimeMillis() - file_idle_timeout)
         {
            Logger.notification("Pending new JAR file: %s", this.jar.getAbsolutePath());
            willBeUpdated = false;
         }
      }

      if (willBeUpdated)
      {
         Logger.notification("Loading new JAR file: %s", this.jar.getAbsolutePath());
         this.prevLastModified = jarLastModified;
      }

      return willBeUpdated;
   }

   @Override
   public ClassLoader createClassLoader()
   {
      final Map resources;

      this.resourceNames.clear();

      try
      {
         resources = this.loadCompleteJarFile();
      }
      catch (IOException exc)
      {
         throw new IllegalStateException("Failed to load JAR file: " + this.jar.getAbsolutePath(), exc);
      }

      this.resourceNames.addAll(resources.keySet());

      ClassLoader loader = new BytesClassLoader(this.getParent())
      {
         @Override
         public byte[] readBytes(String name)
         {
            return resources.get(name);
         }
      };

      return loader;
   }

   private final Map loadCompleteJarFile() throws IOException
   {
      Map map = new HashMap();

      JarFile jf = new JarFile(this.jar);
      Enumeration entries = jf.entries();
      while (entries.hasMoreElements())
      {
         byte[] buf = null;

         JarEntry entry = entries.nextElement();

         if (!entry.isDirectory())
         {
            buf = new byte[(int) entry.getSize()];
            InputStream in = jf.getInputStream(entry);
            int off = 0;
            while (off != buf.length)
            {
               int justRead = in.read(buf, off, buf.length - off);
               if (justRead == -1)
                  throw new EOFException("Could not fully read JAR file entry: " + entry.getName());
               off += justRead;
            }
            in.close();
         }

         map.put(entry.getName(), buf);
      }

      jf.close();

      return map;
   }
}

public abstract class DynamicClassLoader extends ClassLoader
{
   private ClassLoader currentLoader;

   public DynamicClassLoader(ClassLoader parent)
   {
      super(parent);
      this.currentLoader = null;
   }

   //

   public abstract boolean isUpdated();

   public abstract ClassLoader createClassLoader();

   //

   @Override
   public URL getResource(String name)
   {
      this.ensureLatestClassLoader();

      URL url = this.getParent().getResource(name);
      if (url != null)
         return url;

      return this.currentLoader.getResource(name);
   }

   @Override
   public Enumeration getResources(String name) throws IOException
   {
      this.ensureLatestClassLoader();

      Enumeration urls = this.getParent().getResources(name);
      if (urls != null)
         return urls;

      return this.currentLoader.getResources(name);
   }

   @Override
   public InputStream getResourceAsStream(String name)
   {
      this.ensureLatestClassLoader();

      InputStream in = this.getParent().getResourceAsStream(name);
      if (in != null)
         return in;

      return this.currentLoader.getResourceAsStream(name);
   }

   public synchronized Class< ? > loadClass(String name) throws ClassNotFoundException
   {
      this.ensureLatestClassLoader();

      return this.currentLoader.loadClass(name);
   }

   //

   private long lastChecked;
   private long minCheckInterval = 0;

   public void setMinCheckInterval(long minCheckInterval)
   {
      this.minCheckInterval = minCheckInterval;
   }

   public final boolean checkForUpdate()
   {
      long now = System.currentTimeMillis();
      long elapsed = now - this.lastChecked;

      if (elapsed < this.minCheckInterval)
      {
         // if we checked less than N ms ago,
         // just assume the loader is not updated.
         // otherwise we put a major strain on
         // the file system (?) for no real gain
         return false;
      }

      this.lastChecked = now;

      return this.isUpdated();
   }

   //

   public void ensureLatestClassLoader()
   {
      if (this.checkForUpdate())
      {
         this.replaceClassLoader();
      }
   }

   protected void replaceClassLoader()
   {
      this.currentLoader = this.createClassLoader();

      // protected, so do stuff, if you wish
   }
}

public abstract class BytesClassLoader extends ClassLoader
{
   public BytesClassLoader(ClassLoader parent)
   {
      super(parent);
   }
   
   protected abstract byte[] readBytes(String path);

   public synchronized Class< ? > loadClass(String name) throws ClassNotFoundException
   {
      Class< ? > found = this.findLoadedClass(name);
      if (found != null)
      {
         return found;
      }

      String path = name.replace('.', '/').concat(".class");

      byte[] raw = this.readBytes(path);

      if (raw == null)
      {
         return this.getParent().loadClass(name);
      }

      return super.defineClass(name, raw, 0, raw.length);
   }

   @Override
   public InputStream getResourceAsStream(String path)
   {
      byte[] raw = this.readBytes(path);
      if (raw == null)
         return null;
      return new ByteArrayInputStream(raw);
   }

   @Override
   public URL getResource(String name)
   {
      // who uses this anyway?
      throw new UnsupportedOperationException();
   }

   @Override
   public Enumeration getResources(String name) throws IOException
   {
      // who uses this anyway?
      throw new UnsupportedOperationException();
   }
}