From 8b3cc4835c4c77df9f207bd342ffd024f0f726e7 Mon Sep 17 00:00:00 2001 From: iximeow Date: Wed, 26 Nov 2014 00:41:34 -0800 Subject: Rest of challenge 6 also hacking junk around the frequency maps. --- build.sbt | 2 ++ src/utils/ByteUtils.scala | 32 ++++++++++++++++++++++++----- src/utils/ConversionUtils.scala | 1 + src/utils/FrequencyMap.scala | 12 ++++++----- src/utils/StreamUtils.scala | 45 +++++++++++++++++------------------------ 5 files changed, 56 insertions(+), 36 deletions(-) diff --git a/build.sbt b/build.sbt index 533a22b..2913c46 100644 --- a/build.sbt +++ b/build.sbt @@ -15,5 +15,7 @@ initialCommands in console := """ import ixee.cryptopals.utils._ import ByteUtils._ import ConversionUtils._ +import FunctionUtils._ +import StreamUtils._ import ixee.cryptopals.solvers._ """ diff --git a/src/utils/ByteUtils.scala b/src/utils/ByteUtils.scala index 2c51917..18942c0 100644 --- a/src/utils/ByteUtils.scala +++ b/src/utils/ByteUtils.scala @@ -1,6 +1,7 @@ package ixee.cryptopals.utils import FunctionUtils.tup +import ConversionUtils._ object ByteUtils { trait SizedNumeric[T] { @@ -9,8 +10,8 @@ object ByteUtils { def bitSize: Int def fromLong(l: Long): T def toLong(l: T): Long - def buildFrom[U : SizedNumeric](from: U): T = fromLong(from.toLong) - def truncate[U : SizedNumeric](from: U): T = buildFrom(from) + def buildFrom[U : SizedNumeric : BitOps](from: U): T = fromLong(from.toLong) + def truncate[U : SizedNumeric : BitOps](from: U): T = buildFrom(from) override def toString = s"SizedNumeric[${manifest}]" } @@ -21,6 +22,7 @@ object ByteUtils { def @&(a: T, b: T): T def @^(a: T, b: T): T def @+(a: T, b: T): T + def @-(a: T, b: T): T } implicit val byteOps: BitOps[Byte] = new BitOps[Byte] { @@ -30,6 +32,7 @@ object ByteUtils { def @&(a: Byte, b: Byte): Byte = (a & b).toByte def @^(a: Byte, b: Byte): Byte = (a ^ b).toByte def @+(a: Byte, b: Byte): Byte = (a + b).toByte + def @-(a: Byte, b: Byte): Byte = (a - b).toByte } implicit val intOps: BitOps[Int] = new BitOps[Int] { @@ -39,6 +42,7 @@ object ByteUtils { def @&(a: Int, b: Int): Int = a & b def @^(a: Int, b: Int): Int = a ^ b def @+(a: Int, b: Int): Int = a + b + def @-(a: Int, b: Int): Int = a - b } implicit class WithBitOpts[T : BitOps](x: T) { @@ -48,9 +52,10 @@ object ByteUtils { def @&(b: T): T = implicitly[BitOps[T]].@&(x, b) def @^(b: T): T = implicitly[BitOps[T]].@^(x, b) def @+(b: T): T = implicitly[BitOps[T]].@+(x, b) + def @-(b: T): T = implicitly[BitOps[T]].@-(x, b) } - implicit class SizedWithByteInfo[T : SizedNumeric](x: T) { + implicit class SizedWithByteInfo[T : SizedNumeric : BitOps](x: T) { def byteSize = implicitly[SizedNumeric[T]].byteSize def octetSize = byteSize * 2 def bitSize = implicitly[SizedNumeric[T]].bitSize @@ -65,6 +70,17 @@ object ByteUtils { uSize.buildFrom(x) } def hex: String = s"%0${octetSize}x" format x + def bitsSet: Int = { + var bits = 0 + var num = x + + while (num.toLong > 0) { + bits = bits + 1 + num = num @& (num @- 1.truncatedTo[T]) + } + + bits + } def truncatedTo[U : SizedNumeric]: U = { implicitly[SizedNumeric[U]].truncate(x) } @@ -82,8 +98,14 @@ object ByteUtils { implicit val shortized = sizedNumeric(2) { x: Long => x.toShort } { _.toLong } implicit val byteSized = sizedNumeric(1) { x: Long => x.toByte } { _.toLong } - implicit class SeqByteOps(seq: Seq[Byte]) { - def xor(other: Seq[Byte]): Seq[Byte] = + implicit class SeqByteOps[T : SizedNumeric : BitOps](seq: Seq[T]) { + def xor(other: Seq[T]): Seq[T] = seq.zip(other).map(tup(_ @^ _)) } + + def hammingDistance(a: String, b: String): Int = + hammingDistance(a.asBytes, b.asBytes) + + def hammingDistance[T : BitOps : SizedNumeric](a: Seq[T], b: Seq[T]): Int = + (a xor b).map(_.bitsSet).reduce(_ @+ _) } diff --git a/src/utils/ConversionUtils.scala b/src/utils/ConversionUtils.scala index f8935f2..95d08ce 100644 --- a/src/utils/ConversionUtils.scala +++ b/src/utils/ConversionUtils.scala @@ -60,6 +60,7 @@ object ConversionUtils { implicit class RichStringBytes(s: String) { def asBytes = s.toSeq.map(_.toByte) + def asByteStream = s.asBytes.toStream } // TODO: tailrec this, get rid of for diff --git a/src/utils/FrequencyMap.scala b/src/utils/FrequencyMap.scala index fffdabe..e18fd46 100644 --- a/src/utils/FrequencyMap.scala +++ b/src/utils/FrequencyMap.scala @@ -14,7 +14,7 @@ class FrequencyMap(mapargs: Map[Char, Double]) { if (c.isLower) mappings.get(c) else // TODO remove the bias here - mappings.get(c.toLower).map(_ * 0.0002) // bias HARD against uppercase spam. should make this a per-map setting. + mappings.get(c.toLower).map(_ * 0.0004) // bias HARD against uppercase spam. should make this a per-map setting. def diff(other: FrequencyMap): Double = { // pseudoscience here @@ -38,7 +38,7 @@ class FrequencyMap(mapargs: Map[Char, Double]) { def diffAt(c: Char, charFreq: Double) = Math.pow(c match { case ' ' => - squared(0.10 - charFreq) + squared(0.09 - charFreq) case '{' | '}' | '`' | '|' | '^' => squared(0.000001 - charFreq) // { } | and ` are very unlikely irl case '[' | ']' => @@ -46,13 +46,15 @@ class FrequencyMap(mapargs: Map[Char, Double]) { case '"' | '\'' => squared(0.00001 - charFreq) // " or ' are 100% unlikely 90% of the time case '~' | '+' | '=' | '<' | '>' | '/' | '\\' => - squared(0.00000175 - charFreq) // math is weird kids + 1 //squared(charFreq) //squared(0.00000125 - charFreq) // math is weird kids case ';' | ':' | '-' | '*' | '(' | '&' | ')' | '_' => squared(0.000003 - charFreq) // getting into more common punctuation case '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' => squared(0.000002 - charFreq) // numbers are KINDA uncommon - case '$' | '%' | '#' | '@' | '!' => - squared(0.00002 - charFreq) // more punctuation... + case '$' | '%' | '#' | '@' => + 1 //squared(0.00002 - charFreq) // more punctuation... + case '!' => + squared(0.6 - charFreq) case '.' | ',' => squared(0.00007 - charFreq) // and the last of the punctuations case '\n' | '\r' => diff --git a/src/utils/StreamUtils.scala b/src/utils/StreamUtils.scala index cb296d3..4f803c0 100644 --- a/src/utils/StreamUtils.scala +++ b/src/utils/StreamUtils.scala @@ -1,32 +1,25 @@ package ixee.cryptopals.utils +import ixee.cryptopals.utils.FunctionUtils._ + object StreamUtils { implicit class RichStream[A](x: Stream[A]) { - def splice(other: Stream[A]): Stream[A] = { - var i = 0 - val selfIter = x.iterator - val otherIter = other.iterator - Stream.continually { - i = i + 1 - if (i % 2 == 0) { - otherIter.next - } else { - selfIter.next - } - } - } - def spliceEvery(n: Int)(other: Stream[A]): Stream[A] = { - var i = 0 - val selfIter = x.iterator - val otherIter = other.iterator - Stream.continually { - i = i + 1 - if (i % (n + 1) == 0) { - otherIter.next - } else { - selfIter.next - } - } - } + def splice(other: Stream[A]): Stream[A] = + spliceEvery(1)(other) + + def spliceEvery(n: Int)(other: Stream[A]): Stream[A] = + x.grouped(n).zip(other.iterator).flatMap(tup(_ :+ _)).to[Stream] + + def continually: Stream[A] = + x append x.continually } + + def continuous[A](xs: Seq[A]): Stream[A] = + xs.to[Stream] append continuous(xs.to[Stream]) + +/* + // Or just xs.to[Stream] ... + def fromSeq[A](xs: Seq[A]): Stream[A] = + xs.foldLeft(Stream.empty[A])(_ :+ _) +*/ } -- cgit v1.1