bfenc/pybfenc.py

#!/usr/bin/python

#
#	Copyright 2014 Yann Weber <yannweb@member.fsf.org>
#
#	bfstr is free software: you can redistribute it and/or modify
#	it under the terms of the GNU General Public License as published by
#	the Free Software Foundation, either version 3 of the License, or
#(	at your option) any later version.
#
#	bfstr is distributed in the hope that it will be useful,
#	but WITHOUT ANY WARRANTY; without even the implied warranty of
#	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#	GNU General Public License for more details.
#
#	You should have received a copy of the GNU General Public License
#	along with bfstr.  If not, see <http://www.gnu.org/licenses/>.
#

"""
	Brainfuck encoder
"""

import sys
from time import sleep


PRIMES = [ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251 ]

OPTIPRIMEMAX = 21
OPTIDELTAMIN = 26

# Using the generator pattern (an iterable)
class BrainfuckGenerator(object):
	
	def __init__(self,inStr=None):
		self.prev = 0
		self.end = False
		
		if inStr != None:
			self.next(inStr)
			end = True

	def __iter__(self):
		return self

	# Python 3 compatibility
	def __next__(self):
		return self.next()

	def next(self,inStr):
		if self.end:
			raise StopIteration()
			
		res=""
		for c in inStr:
			nc = ord(c)
			plus = True
			delta = nc-self.prev
			
			if delta < 0:
				plus = False
				delta*=-1
				
			if delta > OPTIDELTAMIN:
				res+=nb2bf(delta,plus)
			elif delta > 0:
				if plus:
					chrAdd='+'
				else:
					chrAdd='-'
					
				for _ in range(delta):
					if plus:
						res+=chrAdd
					else:
						res+=chrAdd
			
			
			
			res+='.'
			self.prev = nc
		
		return res

#Function defined only for non generator purpose
def str2bf(inStr):
	bg = bfGen()
	return bg.next(inStr)

#Return the brainfuck ops to add (or sub) delta to the current val
def nb2bf(delta, plus):
	
	primes = primeFact(delta)
	
	#we will test if when adding or substracting 1 is not shorter
	primesP1 = primeFact(delta+1)
	primesM1 = primeFact(delta-1)
	
	p1 = False
	m1 = False
	
	if sum(primes) > sum(primesP1):
		primes = primesP1
		p1=True
	
	if sum(primes) > sum(primesM1) and delta-1>1:
		primes = primesM1
		p1=False
		m1=True
	

	res = ""
	
	mv=0
	
	if len(primes) > 1:
		
		for prime in primes:
			
			mv+=1
			res+='>'
			for _ in range(prime):
				res+='+'
			res+='['

		for _ in range(mv):
			res+='<'
			
		if plus:
			res+='+'
		else:
			res+='-'
			
		for _ in range(mv):
			res+='>'
		res+='-]'
		
		for _ in range(mv-1):
			res+='<-]'
			
		res+='<'
	else:
		for foo in range(primes[0]):
			if plus:
				res+='+'
			else:
				res+='-'
	
	#Correcting the optimisation add 1 or sub 1
	if plus:
		if p1:
			res+='-'
		elif m1:
			res+='+'
	else:
		if p1:
			res+='+'
		elif m1:
			res+='-'
	
	
	return res
		

#Prime factor decomposition
def primeFact(n):
	
	nc = n
	
	res = []
	for i in PRIMES:
		if nc == 0:
			return res
		while nc%i == 0:
			
			#optimization
			if len(res) > 0 and res[-1] * i < OPTIPRIMEMAX:
				res[-1]*=i
			else:
				res.append(i)
				
				
			nc/=i
			
	return res

def main():
	if (len(sys.argv) == 2):	
		print BrainfuckGenerator(sys.argv[1])
	else:
		bg = BrainfuckGenerator()
		for line in sys.stdin:
			sys.stdout.write(bg.next(line))
			sys.stdout.flush()

if __name__ == "__main__":
	main()