import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

class TinyCipher implements Cipher {
	
	private static final int ROUNDS = 12;
	
	private final int b;
	private final int b_l;
	private final int b_r;
	private final byte[] k;
	private final MessageDigest sha1;
	
	public TinyCipher(int numBits, byte[] key) {
		this.b = numBits;
		this.b_l = numBits / 2;
		this.b_r = numBits - b_l;
		assert this.b_r >= this.b_l;
		this.k = key;
		try {
			this.sha1 = MessageDigest.getInstance("SHA");
		}
		catch (NoSuchAlgorithmException e) {
			throw new RuntimeException("violation of Java Cryptography Architecture API Specification - Appendix A", e);
		}
	}
	
	public int encrypt(int x) {
		for (int round = 0; round < ROUNDS; ++round) {
			int l = (x >>> b_r); // no mask needed, because top bits all zero
			int r = x & mask(b_r);
			l = (l + roundKey(round, r)) & mask(b_l);
			x = (r << b_l) + l;
		}
		return x;
	}
	
	public int decrypt(int x) {
		for (int round = ROUNDS - 1; round >= 0; --round) {
			int l = x & mask(b_l);
			int r = (x >>> b_l); // no mask needed, because top bits all zero
			l = (l - roundKey(round, r)) & mask(b_l);
			x = (l << b_r) + r;
		}
		return x;
	}
	
	private int mask(int nbits) {
		return (1 << nbits) - 1;
	}
	
	private int roundKey(int round, int x) {
		sha1.reset();
		sha1.update((byte)round); // assume round < 256
		sha1.update(k);
		int rbytes = ((b_r - 1) / 8) + 1;
		for (int i = 0; i < rbytes; ++i) {
			sha1.update((byte)(x >>> (((rbytes - i) - 1) * 8)));
		}
		byte[] hash = sha1.digest();
		int z = 0;
		int lbytes = ((b_l - 1) / 8) + 1;
		for (int i = 0; i < lbytes; ++i) {
			z = (z << 8) + (hash[i] & 0xff);
		}
		z = z >>> ((lbytes * 8) - b_l); // throw away excess bits!
		return z;
	}
	
}