# New Spoken Passage in Xazik

Here’s a spoken passage from the traditional wisdom literature in the native Xazik tongue. The utterance was performed by David Silo.

# Proto-Indo-European Being Spoken

Check out the audio file of the King and the God being read in Proto-Indo-European. It sounds very authentic and phonologically sound. I didn’t want to loose the sound file so I’ve linked it here. Enjoy!

# Design Patterns in D: Introduction

Design Patterns (Photo credit: Wikipedia)

[starreview tpl=16 style=’starscape’]

This and the posts to follow on this topic are a mix of two of my favorite software engineering topics: design and the D programming language. In particular, I’ll be discussing design patterns as first revealed and described by the “Gang of Four”[1. Gamma, E., Helm R., Johnson R., Vlissides J. (2004) Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesely.]. In this, the first of the series, I’ll briefly cover some ground on the necessary and essential background information you’ll need to make sense of it.

# Background: Design Patterns

A “pattern” is

a way of doing something, or a way of pursuing an intent; a standardized way of achieving a certain aim.

This applies equally to all things from cooking, to painting, to writing software. In software engineering, design patterns offer two main benefits:

1. they provide a way to solve related issues using a proven and tested solution, allowing the development of highly cohesive, encapsulated modules with a minimum of coupling.
2. they make communication of sometimes complex subjects among software engineers more efficient and true.

## Coupling vs. Cohesion

Coupling: When two compilation units depend on each other. One unit (or both) are highly connected with a change in one rippling through the other. Coupling is a Bad Thing™ because:

• the units are overly complicated and difficult to understand
• locating faults is tedious and error prone
• difficult to extend or enhance
• low reusability
• evinces a heavy maintenance cost

Cohesion: each function, class, struct, etc should only do one thing. A highly cohesive unit is typically much easier to grok.

# Background: D Programming Language

There are several excellent sources available for studying and applying design patterns in a number of popular programming languages like Java, C++, Perl, Python, etc. I haven’t seen one for D, so I thought I’d write up some stuff and see where it takes me.

The D programming language is a low-level system programming language that supports:

• automatic garbage collection
• function delegates
• interfaces and multiple inheritance
• compile-time evaluation
• built-in strings, arrays, and associative arrays
• generic (template, too) programming concepts (ie metaprogramming)
• contract-style programming
• RAII
• exceptions and robust error handling
• wide compatibility, even at the binary object level with C++ and C

The official website for D is http://www.dlang.org

# Pattern Classification

Patterns themselves are organized into groups of patterns that share the same set of properties. The three major design pattern classifications are:

1. Creational Patterns
Deal with object creation patterns and mechanisms. Guides how to create objects when their creation requires logic or decision making. Encapsulates knowledge about which concrete classes the system uses. Hide or otherwise conceal the exact process through which an object comes into being. Creational patterns come in two flavors: class and object. Class creational patterns use inheritance to vary the class that is instantiated. Object creational patterns delegate instantiation to another object.

2. Structural Patterns
Describe how classes and objects can be combined into larger aggregate or composite structures. Eases the design by identifying a simple way to realize relationships between entities. Provides data encapsulation such that changes to one unit doesn’t propagate through unrelated but connected units.

• Bridge
• Composite
• Decorator
• Flyweight
• Proxy
3. Behavioral Patterns
Concerned specifically with communication and behavior between and among objects. Also two flavors: class and object. Behavior classes use inheritance to distribute behavior between classes while behavioral object patterns use composition instead of inheritance.

• Command
• Interpreter
• Iterator
• Mediator
• Memento
• Observer
• State
• Strategy
• Template
• Visitor
• Chain of Responsibility

That’s it for the introduction to software design patterns…for now. Stay tuned for the next installment where I discuss individual patterns in greater detail and how to implement them in D.

Cheers!
Gian

# Printing From an Arduino/AVR

AVR logo. (Photo credit: Wikipedia)

If you’re like me, you have a lot of old classic equipment. Besides my beat-to-death Honeywell CP/M and oft-never-found TRS-80, I have a ton of other old gear like ISA 10bT NICs, VESA and Hercules graphics cards, 400MB IDE hard drives, just to name a few. Well, while digging through my junk looking for my I-can-never-find-this-when-I-need it 16-connector flat ribbon spool, I ran across my old Epson LQ-570+ impact printer (ie dot matrix).

I pulled it out from the 386sx and 486dx under which it was cleverly residing in a neglected state of repose and brought it into my shop. I plugged it in and green blinkin lights came on, the printer head did a whirley whirl thingo and I so bravely went to plug it into the back of one of my workstations and, of course, no compatible I/O ports. This thing connects via a 36-pin centronix to a 25-pin D-sub parallel port socket. But wait, don’t I have one or three of those 25-pin D-subs in straight and right angle packages in one of my drawers of rectangular connectors? Why yes, yes I do.

Unable to wait until I could hook it up to a PC proper (assuming I could even get drivers for my OS), I quickly went about designing an AVR-to-DotMatrix interface. I thought maybe I could have the AVR listen on it’s USART and print what I type to it, but then I bleched at the idea and thought a more generic use of the printer was in order. Instead of printing out to, say, a 2-line, 24 character LCD or some such, why not have the option to just print directly to the printer? Oh yeah, my retro rebuild and reboot feeling was coming on strong.

The direction and pin signals follow like this:

## Interface Specifications

Data Format: 8-bit parallel
Synchronization: !STROBE pulse
Handshaking: BUSY and !ACK
Signal Level: TTL
Connector: 36-pin Centronix to 25-pin D-sub parallel

# ESC/P* Programming Introduction

Epson, and particularly, this model LQ-570+ uses what is called ESC/P2 (or more simply, ESC/P) programming. A series of ESC and operands are sent and received to and from the computer for normal operation and other such things. But I’m getting ahead of myself. My first course of action is to make a breakout board for my DB25 parallel port socket and some pin headers that are easily attachable to my Arduino or bare AVR.

Cheers!

Gian

# Flash Memory

Flash memory is non-volatile storage on a chip that can be electrically erased and programmed. Flash memory has recently improved to support much larger densities than before, making it a viable secondary storage facility. However, flash memory just like EEPROM, has a stated endurance. The endurance of the flash memory is how many times a unit of memory can be written/erased before failing. The endurance rating is typically measured in the 10,000 to 1,000,000 write/erases range. While the boot/root filesystem is not envisioned to change very much once frozen, there may always be multiple changes while going through release iterations. Therefore, the design of this type of secondary storage should support easy attachment and detachment (ie replacement) to the main board. This means it should probably be built on a separate, detachable/insertable PCB.

Another unique facet of using Flash memory and not a traditional hard drive is the fact that you cannot overwrite data on a Flash chip, you have to erase it first. In other words, even “dead pages” cannot be used even if it contains all unused or out-of-data data until that block has been erased first. Therefore, a common strategy of garbage collection is used to manage free and allocated blocks on the flash chip.

The access time of flash memory can be as good as 8ns (or maybe better) to 20ns. This is fast enough for our purposes.

The specified amount of Flash memory for secondary storage is 256Mbit (32MB) in the SOIC-16 package (or MLP8/8SON,V-PDFN8 if the landings are workable by hand soldering).

Due to the low amount of intended writes and erases on these ICs, we may not need to create a separate detachable card if we only put a mostly immutable (or mostly changeless) root file system on it and having an external SD card contain the parts of the file system that are written to and erased most often.

The SIP card to the right is the current incarnation of the on-board (mostly) immutable data flash. It is envisioned and planned that there will not be so many erase/writes from these flash chips to ever cause you to have to replace them, but they’re on a 12-pin SIP package board for easily adding and removing the flash chips if the need arises. Production machines should never have to replace their on-board flash, but development workstations just possibly might, since we’ll be iterating through numerous revisions and releases that will potentially cause the root filesystem to be erased and rewritten many times. But if you’re not a developer you probably don’t have to worry about this.

The flash SIP card to the right holds four 128Mbit (16MB) flash chips giving the system root flash a grand total of 64MB of non-volatile storage to use for mostly root filesystem purposes.

Flash storage comes in two flavors: NAND and NOR. In both types, write operations can only clear bits and the only way to set bits is to erase entire region of memory, typically in block or page size.

## NAND

NAND is the recent addition to the family, and it works much like the block devices such as hard disks. It is normally partitioned and used as file systems. Normally, NAND flashes are divided into blocks that work as erase units and each block consists of several pages. Read/write opera-tions are handled per page and hence, while considering NAND flashes for the proposed data structure the only concern is the page size. Typical page size of NAND flash is 512 bytes; where block size is about 16K bytes.

NAND Flash was developed as an alternative optimized for high-density data storage, giving up random access capability in a tradeoff to achieve a smaller cell size, which translates to a smaller chip size and lower cost-per-bit. This was achieved by creating an array of eight memory transistors connected in a series. Utilizing the NAND Flash architecture’s high storage density and smaller cell size, NAND Flash systems enable faster write and erase by programming blocks of data. NAND Flash is ideal for low-cost, high-density, high-speed program/erase applications, often referred to as data-storage applications.

## NOR

NOR flash is the older of the two types and provides random access. It can be addressed at byte level from CPU and can be used as RAM, if needed. It is very slow to write and hence, normally used as storage for static data. This property of addressing at byte level makes it suitable for storing the nodes of the trie.

In the internal circuit configuration of NOR Flash, the individual memory cells are connected in parallel, which enables the device to achieve random access. This configuration enables the short read times required for the random access of microprocessor instructions. NOR Flash is ideal for lower-density, high-speed read applications, which are mostly read only, often referred to as code-storage applications.

## NAND vs. NOR Flash Memories

 NAND NOR XIP (execute in place) allowing an app to be run directly from flash w/o having to load into RAM (not sure this matters for our MCUs anyway) Fast write and erase rates High READ performance but poor WRITE/ERASE performance High cell densities Most cost effective in smaller densities <= 4Mbit Greater need for flash management, wear leveling, etc Erase before write straightforward without special requirementts Erase before write mandates that all bytes in target block bet written with zeros before erasure. erase blocks 8-32KB typical erase blocks 64-128KB typical* ~1M erase cycle endurance 100K erase cycle endurance “bit flip/reverse” errors more common “bit flip” errors less common, better error rates for critical storage subsystems (ie /root) has a particular bad block management requirement

### At a Glance

• NOR reads slightly faster than

English: I, § Music Sorter § (talk) 04:56, 18 June 2010 (UTC), created and uploaded this drawing into Wikipedia under the Creative Commons Attribution-ShareAlike 3.0 License. This drawing illustrates the difference between data written to NAND Flash memory in 4 KB pages and data erased in 256 KB blocks. (Photo credit: Wikipedia)

NAND.

• NAND writes significantly faster than NOR.
• NAND erases much faster than NOR–4 ms vs. 5 s, respectively.
• Most writes require a preceding erase operation.
• NAND has smaller erase units, so fewer erases are needed.

* must verify this

 PARAMETER NOR NAND Capacity 1 to 16 Mbytes 8 to 128 Mbytes XIP (code execution) Yes No PerformanceErase Write Read Very Slow (5 s) Slow Fast Fast (3 ms) Fast Fast Strengths Addressable to every byte More than 10% higher life expectancy Erase cycle range 10,000 to 100,000 100,000 to1,000,000 Interface SRAM-like, memory mapped Accessed in bursts of 512 bytes; I/O mapped Access method Random Sequential Price High Very low

The root filesystem data flash storage is specified to be NOR at least for production runs. We don’t have to have fast write for development purposes, but a fast read is essential.

## Lessons Learned

• Log based FFS
• ↑ flash density, ↑ mount time to identify metadata contents
• ↑ RAM requirements to store mapping in core
• Some Possible Improvements
• Hashing directory structure for directory management
• Two level index structure for file index managmeent
• Reduces mount time and memory footprint
• JFFS2
• metadata and versioning data written in free data node in sequential manner
• need to scan entire flash media at mount time
• YAFFS/2
• file id (inode) and chunk number stored in spare region
• need to scan spare region only (inverse mapping)
• faster than JFFS2
• CFFS
• inode map block: dedicated flash region
• inode block hash in core
• pseudo hot-cold separation
• enhanced mount time and memory footprint
• Some Possible Improvements
• Hashing directory structure for directory management
• Two level index structure for file index managmeent
• Reduces mount time and memory footprint
• reduce additional page consumption when file is created or written
• separation of data and metadata block
• Block types
• hashing directory blocks: hashing table of directories
• inode blocks: file’s inode
• data blocks: file’s real data
• super block: map of blocks

The implementation of the filesystem in munix isn’t trivial, but armed with the aforementioned knowledge, it will allow me to create a fast, responsive, and reliable filesystem, tailored to the indiosynchrasies of flash-based secondary storage while being exceedingly parsimonious with system RAM and resources.

Stay tuned for the upcoming parts of this post and updates relating to how the filesystem is going!

# Finding All Defined Macros in (avr-)gcc

Have you ever scratched your head during a coding session and needed to know how or if a particular item is defined and known/understood by your GCC compiler? For instance, I often need to know what host operating system I’m on. Should i do a

#ifdef __windows__
...
#elsif defined(__linux)
...
#else // defined(__avr__)
...
#endif

or which preprocessor directives are defined? Did it have two underscores in front of it or just one? Did it have any trailing underscores? How about capitalization? These questions can drive you mad!

$avr-gcc -dM -E – < /dev/null and you’ll get output something like this: #define PORT0 0 #define __LPM_classic__(addr) (__extension__({ uint16_t __addr16 = (uint16_t)(addr); uint8_t __result; __asm__ ( "lpm" "\n\t" "mov %0, r0" "\n\t" : "=r" (__result) : "z" (__addr16) : "r0" ); __result; })) #define __DBL_MIN_EXP__ (-125) #define __UINT_LEAST16_MAX__ 65535U #define __ATOMIC_ACQUIRE 2 #define __FLT_MIN__ 1.17549435e-38F #define __BUILTIN_AVR_SLEEP 1 #define __UINT_LEAST8_TYPE__ unsigned char #define _T_WCHAR_ #define LOCKMEM __attribute__((section (".lock"))) #define __INTMAX_C(c) c ## LL #define __CHAR_BIT__ 8 #define __UINT8_MAX__ 255 #define __WINT_MAX__ 65535U #define stderr (__iob[2]) #define va_start(v,l) __builtin_va_start(v,l) #define __ORDER_LITTLE_ENDIAN__ 1234 #define __SIZE_MAX__ 65535U #define __WCHAR_MAX__ 32767 #define _FARTHER_COMMON_ID "$Id: common.h 69249 2012-08-28 18:42:19Z unknown $" #define __DBL_DENORM_MIN__ double(1.40129846e-45L) #define __GCC_ATOMIC_CHAR_LOCK_FREE 1 #define SREG_C (0) #define SREG_H (5) #define SREG_I (7) #define SREG_N (2) #define SREG_S (4) #define SREG_T (6) #define __FLT_EVAL_METHOD__ 0 #define SREG_V (3) #define SREG_Z (1) #define fdev_close() ((void)0) #define Max(x,y) ((x)>=(y)?(x):(y)) #define __GCC_ATOMIC_CHAR32_T_LOCK_FREE 1 #define HEAP_END() (__malloc_heap_end) #define __UINT_FAST64_MAX__ 18446744073709551615ULL #define __SIG_ATOMIC_TYPE__ int #define __DBL_MIN_10_EXP__ (-37) #define __FINITE_MATH_ONLY__ 0 #define __STDDEF_H__ #define DTOSTR_ALWAYS_SIGN 0x01 #define __GNUC_PATCHLEVEL__ 0 #define Min(x,y) ((x)<=(y)?(x):(y)) #define __UINT_FAST8_MAX__ 65535U #define __size_t #define PIN0 0 #define PIN1 1 #define PIN2 2 #define PIN3 3 #define PIN4 4 #define PIN5 5 #define PIN6 6 #define PIN7 7 #define __DEC64_MAX_EXP__ 385 #define _WCHAR_T_DEFINED #define __INT8_C(c) c #define __UINT_LEAST64_MAX__ 18446744073709551615ULL #define _AVR_FUSE_H_ 1 #define __SHRT_MAX__ 32767 #define __LDBL_MAX__ 3.40282347e+38L #define BTOG(ADDRESS,BIT) (ADDRESS ^= (unsigned char)(1<<BIT)) #define BIT8(b) (0x01 << (b)) #define __UINT_LEAST8_MAX__ 255 #define __GCC_ATOMIC_BOOL_LOCK_FREE 1 #define __ptr_t void * #define __UINTMAX_TYPE__ long long unsigned int #define __BUILTIN_AVR_DELAY_CYCLES 1 #define __DEC32_EPSILON__ 1E-6DF #define bit_is_clear(sfr,bit) (!(_SFR_BYTE(sfr) & _BV(bit))) #define putchar(__c) fputc(__c, stdout) #define __UINT32_MAX__ 4294967295UL #define getc(__stream) fgetc(__stream) #define __SIZE_T #define __LDBL_MAX_EXP__ 128 #define __WINT_MIN__ 0U #define fdev_setup_stream(stream,p,g,f) do { (stream)->put = p; (stream)->get = g; (stream)->flags = f; (stream)->udata = 0; } while(0) #define nop() (asm volatile("nop\n\t"::)) #define _SIZE_T_DEFINED_ #define _SFR_IO8(io_addr) _MMIO_BYTE((io_addr) + __SFR_OFFSET) #define __SCHAR_MAX__ 127 #define __WCHAR_MIN__ (-__WCHAR_MAX__ - 1) #define clearerror(s) do { (s)->flags &= ~(__SERR | __SEOF); } while(0) #define __INT64_C(c) c ## LL #define __DBL_DIG__ 6 #define __AVR_LIBC_VERSION__ 10800UL #define _AVR_PORTPINS_H_ 1 #define __GCC_ATOMIC_POINTER_LOCK_FREE 1 #define BMSET(x,y) (x |= (y)) #define __AVR_LIBC_DATE_ 20111228UL #define getchar() fgetc(stdin) #define __SIZEOF_INT__ 2 #define __SIZEOF_POINTER__ 2 #define __GCC_ATOMIC_CHAR16_T_LOCK_FREE 1 #define __USER_LABEL_PREFIX__ #define __CONCAT(left,right) __CONCATenate(left, right) #define _FDEV_SETUP_WRITE __SWR #define __STDC_HOSTED__ 1 #define __LDBL_HAS_INFINITY__ 1 #define _STDIO_H_ 1 #define __AVR_LIBC_MAJOR__ 1 #define _SFR_MEM_ADDR(sfr) ((uint16_t) &(sfr)) #define __ATTR_PROGMEM__ __attribute__((__progmem__)) #define _BSD_SIZE_T_DEFINED_ #define __FLT_EPSILON__ 1.19209290e-7F #define __GXX_WEAK__ 1 #define _MMIO_BYTE(mem_addr) (*(volatile uint8_t *)(mem_addr)) #define __LDBL_MIN__ 1.17549435e-38L #define AVR_STATUS_REG SREG #define FNAME() (std::cout << __PRETTY_FUNCTION__ << std::endl) #define __AVR_SFR_OFFSET__ 0x20 #define __DEC32_MAX__ 9.999999E96DF #define LOCKBITS_DEFAULT (0xFF) #define _WCHAR_T_ #define __AVR_LIBC_VERSION_STRING__ "1.8.0" #define _STDDEF_H #define __INT32_MAX__ 2147483647L #define __SFR_OFFSET 0x20 #define __SIZEOF_LONG__ 4 #define __UINT16_C(c) c ## U #define __DECIMAL_DIG__ 9 #define __AVR_2_BYTE_PC__ 1 #define __ATTR_CONST__ __attribute__((__const__)) #define _VECTOR(N) __vector_ ## N #define PROGMEM __ATTR_PROGMEM__ #define __LDBL_HAS_QUIET_NAN__ 1 #define _SFR_MEM8(mem_addr) _MMIO_BYTE(mem_addr) #define __BUILTIN_AVR_SEI 1 #define ___int_wchar_t_h #define _T_PTRDIFF #define __GNUC__ 4 #define offsetof(TYPE,MEMBER) __builtin_offsetof (TYPE, MEMBER) #define _ODS_COMMON_H_ #define __BUILTIN_AVR_SWAP 1 #define __FLT_HAS_DENORM__ 1 #define __SIZEOF_LONG_DOUBLE__ 4 #define _FDEV_SETUP_RW (__SRD|__SWR) #define SEEK_CUR 1 #define __BIGGEST_ALIGNMENT__ 1 #define loop_until_bit_is_clear(sfr,bit) do { } while (bit_is_set(sfr, bit)) #define __UINT24_MAX__ 16777215UL #define BEGIN_CRITICAL_SECTION() #define __GNUG__ 4 #define __LONG_LONG_MAX__ 9223372036854775807LL #define __SIZEOF_SIZE_T__ 2 #define __SIZEOF_WINT_T__ 2 #define __GXX_ABI_VERSION 1002 #define __INT24_MAX__ 8388607L #define __FLT_MIN_EXP__ (-125) #define __INT_FAST64_TYPE__ long long int #define __DBL_MIN__ double(1.17549435e-38L) #define __USING_MINT8 0 #define __FLT_MIN_10_EXP__ (-37) #define __DEC128_MIN__ 1E-6143DL #define __REGISTER_PREFIX__ #define __UINT16_MAX__ 65535U #define __DBL_HAS_DENORM__ 1 #define __AVR_ARCH__ 2 #define __UINT8_TYPE__ unsigned char #define __NO_INLINE__ 1 #define __FLT_MANT_DIG__ 24 #define __VERSION__ "4.7.0" #define __UINT64_C(c) c ## ULL #define __GCC_ATOMIC_INT_LOCK_FREE 1 #define __FLOAT_WORD_ORDER__ __ORDER_LITTLE_ENDIAN__ #define __CONCATenate(left,right) left ## right #define __INT32_C(c) c ## L #define __DEC64_EPSILON__ 1E-15DD #define __ORDER_PDP_ENDIAN__ 3412 #define __DEC128_MIN_EXP__ (-6142) #define __INT_FAST32_TYPE__ long int #define __UINT_LEAST16_TYPE__ short unsigned int #define __INT16_MAX__ 32767 #define __SIZE_TYPE__ unsigned int #define __UINT64_MAX__ 18446744073709551615ULL #define __INT8_TYPE__ signed char #define __ELF__ 1 #define __FLT_RADIX__ 2 #define __INT_LEAST16_TYPE__ short int #define __LDBL_EPSILON__ 1.19209290e-7L #define __UINTMAX_C(c) c ## ULL #define __INT24_MIN__ (-__INT24_MAX__-1) #define __SIG_ATOMIC_MAX__ 32767 #define __GCC_ATOMIC_WCHAR_T_LOCK_FREE 1 #define __SIZEOF_PTRDIFF_T__ 2 #define __AVR 1 #define __DEC32_SUBNORMAL_MIN__ 0.000001E-95DF #define __INT_FAST16_MAX__ 32767 #define __UINT_FAST32_MAX__ 4294967295UL #define __UINT_LEAST64_TYPE__ long long unsigned int #define __FLT_HAS_QUIET_NAN__ 1 #define __FLT_MAX_10_EXP__ 38 #define __LONG_MAX__ 2147483647L #define __DEC128_SUBNORMAL_MIN__ 0.000000000000000000000000000000001E-6143DL #define __FLT_HAS_INFINITY__ 1 #define __UINT_FAST16_TYPE__ unsigned int #define __DEC64_MAX__ 9.999999999999999E384DD #define __CHAR16_TYPE__ short unsigned int #define __PRAGMA_REDEFINE_EXTNAME 1 #define __STDINT_H_ #define __INT_LEAST16_MAX__ 32767 #define __DEC64_MANT_DIG__ 16 #define __UINT_LEAST32_MAX__ 4294967295UL #define SCAN_HPP_ #define __GCC_ATOMIC_LONG_LOCK_FREE 1 #define __INT_LEAST64_TYPE__ long long int #define __INT16_TYPE__ short int #define __INT_LEAST8_TYPE__ signed char #define __DEC32_MAX_EXP__ 97 #define __INT_FAST8_MAX__ 32767 #define __INTPTR_MAX__ 32767 #define __AVR_ERRATA_SKIP__ 1 #define __LDBL_MANT_DIG__ 24 #define __DBL_HAS_QUIET_NAN__ 1 #define __SIG_ATOMIC_MIN__ (-__SIG_ATOMIC_MAX__ - 1) #define AVR 1 #define __BUILTIN_AVR_FMULS 1 #define __INTPTR_TYPE__ int #define __UINT16_TYPE__ short unsigned int #define __WCHAR_TYPE__ int #define __SIZEOF_FLOAT__ 4 #define __AVR__ 1 #define __BUILTIN_AVR_INSERT_BITS 1 #define __UINTPTR_MAX__ 65535U #define __DEC64_MIN_EXP__ (-382) #define __INT_FAST64_MAX__ 9223372036854775807LL #define __GCC_ATOMIC_TEST_AND_SET_TRUEVAL 1 #define __FLT_DIG__ 6 #define __UINT_FAST64_TYPE__ long long unsigned int #define __INT_MAX__ 32767 #define __INT64_TYPE__ long long int #define __FLT_MAX_EXP__ 128 #define __DBL_MANT_DIG__ 24 #define __INT_LEAST64_MAX__ 9223372036854775807LL #define __DEC64_MIN__ 1E-383DD #define __WINT_TYPE__ unsigned int #define __UINT_LEAST32_TYPE__ long unsigned int #define __SIZEOF_SHORT__ 2 #define __LDBL_MIN_EXP__ (-125) #define __INT_LEAST8_MAX__ 127 #define __LDBL_MAX_10_EXP__ 38 #define __ATOMIC_RELAXED 0 #define __DBL_EPSILON__ double(1.19209290e-7L) #define __UINT8_C(c) c #define __INT_LEAST32_TYPE__ long int #define __SIZEOF_WCHAR_T__ 2 #define __UINT64_TYPE__ long long unsigned int #define __INT_FAST8_TYPE__ int #define __DBL_DECIMAL_DIG__ 9 #define __DEC_EVAL_METHOD__ 2 #define __ORDER_BIG_ENDIAN__ 4321 #define __UINT32_C(c) c ## UL #define __INTMAX_MAX__ 9223372036854775807LL #define __BYTE_ORDER__ __ORDER_LITTLE_ENDIAN__ #define __FLT_DENORM_MIN__ 1.40129846e-45F #define __INT8_MAX__ 127 #define __UINT_FAST32_TYPE__ long unsigned int #define __CHAR32_TYPE__ long unsigned int #define __FLT_MAX__ 3.40282347e+38F #define __INT32_TYPE__ long int #define __SIZEOF_DOUBLE__ 4 #define __INTMAX_TYPE__ long long int #define __DEC128_MAX_EXP__ 6145 #define __AVR_HAVE_16BIT_SP__ 1 #define __ATOMIC_CONSUME 1 #define __GNUC_MINOR__ 7 #define __UINTMAX_MAX__ 18446744073709551615ULL #define __DEC32_MANT_DIG__ 7 #define __BUILTIN_AVR_CLI 1 #define __DBL_MAX_10_EXP__ 38 #define __LDBL_DENORM_MIN__ 1.40129846e-45L #define __INT16_C(c) c #define __STDC__ 1 #define __PTRDIFF_TYPE__ int #define __ATOMIC_SEQ_CST 5 #define __UINT32_TYPE__ long unsigned int #define __UINTPTR_TYPE__ unsigned int #define __DEC64_SUBNORMAL_MIN__ 0.000000000000001E-383DD #define __DEC128_MANT_DIG__ 34 #define __LDBL_MIN_10_EXP__ (-37) #define __SIZEOF_LONG_LONG__ 8 #define __GCC_ATOMIC_LLONG_LOCK_FREE 1 #define __LDBL_DIG__ 6 #define __FLT_DECIMAL_DIG__ 9 #define __UINT_FAST16_MAX__ 65535U #define __GNUC_GNU_INLINE__ 1 #define __GCC_ATOMIC_SHORT_LOCK_FREE 1 #define __BUILTIN_AVR_FLASH_SEGMENT 1 #define __UINT_FAST8_TYPE__ unsigned int #define __ATOMIC_ACQ_REL 4 #define __ATOMIC_RELEASE 3 #define __BUILTIN_AVR_FMUL 1  That should work for you to get any architecture-dependent preprocessor defines that you might need, like in my case here __AVR__ or even the specific AVR architecture itself, as with __AVR_ARCH__ or the bit width of the internal stack pointer SP with __AVR_HAVE_16B_SP__! All good things to know! Enjoy! -gian # Fuzzifier for Fuzzy Sets on AVR Hi again, I recently wrote a fuzzifier in C++ for an online game project I’ve been working on. Then, for fun, I made a few tweaks to the code and compiled it as a static application and flashed it on an Atmel ATmega644P AVR microcontroller. The output was simple ASCII text via the serial USART. I have written extensively about setting up USART serial communication on AVRs elsewhere so I don’t cover that here. This is just concerning the fuzzy bit. # The Categories In this test example, I created four fuzzy categories: very small, small, medium, and large. They are shown in the chart below. You can see from the graph that a value may have membership in upwards of three different categories. In this case, the requirement is for the probability for all memberships to add to one. To find the percentage probability from the graph, take the height of each curve at a given value and normalize this to a one-unit length. fuzzy.hpp #ifndef _GOVT_FUZZY_HPP_ #define _GOVT_FUZZY_HPP_ /******************************************************************************* ** Government Sanctioned Espionage RPG ** ** http://www.government-sanctioned.us/ ** **===========================================================================** ** Name: fuzzy.hpp ** ** Description: Fuzzy logic sets. ** ** ** ** Open Source Initiative (OSI) Approved License ** ** ** ** The contents of this file are subject to the terms of the ** ** Common Development and Distribution License, Version 1.0 only ** ** (the "License"). You may not use this file except in compliance ** ** with the License. ** ** ** ** You can find a copy of the license in the LICENSE file within ** ** this distribution or at$WIKI/display/GOVT/License-software.              **
** basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.           **
** See the License for the specific language governing permissions           **
** and limitations under the License.                                        **
**                                                                           **
** When distributing Covered Code, include this CDDL header in each          **
** file and include the License file at $GAME_DIR/LICENSE. ** ** If applicable, add the following below this header, with the indicated ** ** fields enclosed by brackets "[]" replaced with your own identifying ** ** information: Portions Copyright [yyyy] [name of copyright owner] ** ** ** ** Copyright (c) 2009-2012 Barry Gian James <gian@gamingods.net> ** ** All rights reserved. ** ******************************************************************************/ //$Id$// Modified$Date$by$Author$#include <string> namespace fuzzy { //! @class category //! @brief Implements fuzzy categories with variable membership values class category { public: category(std::string n, double l, double m, double h) : _low(l), _mid(m), _high(h) { _name = n; } category() { } std::string & name() { return _name; } void range(double l, double m, double h) { _low = l; _mid = m; _high = h; } double low() { return _low; } double mid() { return _mid; } double high() { return _high; } double membership(double); private: std::string _name; double _low, _mid, _high; }; } /* namespace fuzzy */ #endif /* _GOVT_FUZZY_HPP_ */ fuzzy.cpp /******************************************************************************* ** Government Sanctioned Espionage RPG ** ** http://www.government-sanctioned.us/ ** **===========================================================================** ** Name: fuzzy.cpp ** ** Description: Fuzzy logic sets. ** ** ** ** Open Source Initiative (OSI) Approved License ** ** ** ** The contents of this file are subject to the terms of the ** ** Common Development and Distribution License, Version 1.0 only ** ** (the "License"). You may not use this file except in compliance ** ** with the License. ** ** ** ** You can find a copy of the license in the LICENSE file within ** ** this distribution or at$WIKI/display/GOVT/License-software.              **
** basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.           **
** See the License for the specific language governing permissions           **
** and limitations under the License.                                        **
**                                                                           **
** When distributing Covered Code, include this CDDL header in each          **
** file and include the License file at $GAME_DIR/LICENSE. ** ** If applicable, add the following below this header, with the indicated ** ** fields enclosed by brackets "[]" replaced with your own identifying ** ** information: Portions Copyright [yyyy] [name of copyright owner] ** ** ** ** Copyright (c) 2009-2012 Barry Gian James <gian@gamingods.net> ** ** All rights reserved. ** ******************************************************************************/ //$Id$// Modified$Date$by$Author\$

#include "fuzzy.hpp"

namespace fuzzy
{

double
category::membership(double i)
{
double output, midlow, highmid;

midlow = _mid - _low;
highmid = _high - _mid;

if ( (i <= _low) || (i >= _high) )
output = 0;
else
{
if (i > _mid)
output = (_high - i)/highmid;
else if (i == _mid)
output = 1.0;
else
output = (i - _low)/midlow;
}
return output;
}

}	/* namespace fuzzy */

And that’s about all you need to start fuzzifying data for fuzzy categories on an AVR!

Gian

# For a Love of Numbers #1: Sequences

Hello and welcome,

This is the first post in a series of posts on numbers, number theory, and math. In this post, I cover some basic sequences. Expand the content below to explore these sequences[1. The code and output is done in the R statistical programming language]. All sequences, unless otherwise noted, include the first 50 numbers in the sequence. Where found, images are included from screen captures on my TI-nspire CX calculator.

[sections] [section title=”Natural Numbers”]
> sequence <- 1:50
> sequence
[1]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19
[20] 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
[39] 39 40 41 42 43 44 45 46 47 48 49 50
[/section] [section title=”Even Numbers”]
> 2*sequence
[1]   2   4   6   8  10  12  14  16  18  20  22  24  26  28
[15]  30  32  34  36  38  40  42  44  46  48  50  52  54  56
[29]  58  60  62  64  66  68  70  72  74  76  78  80  82  84
[43]  86  88  90  92  94  96  98 100
[/section] [/section] [section title=”Odd Numbers”] [info]2n – 1[/info]
> 2*sequence - 1
[1]  1  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37
[20] 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75
[39] 77 79 81 83 85 87 89 91 93 95 97 99
[/section] [section title=”Multiples of 3 plus 1″]
> 3*sequence+1
[1]   4   7  10  13  16  19  22  25  28  31  34  37  40  43
[15]  46  49  52  55  58  61  64  67  70  73  76  79  82  85
[29]  88  91  94  97 100 103 106 109 112 115 118 121 124 127
[43] 130 133 136 139 142 145 148 151
[/section] [section title=”Powers of 2″] [info]$$2^{n-1}$$ This is really useful if you’re working with binary data or bits of bytes.[/info]
> 2^(sequence-1)
[1] 1.000000e+00 2.000000e+00 4.000000e+00 8.000000e+00
[5] 1.600000e+01 3.200000e+01 6.400000e+01 1.280000e+02
[9] 2.560000e+02 5.120000e+02 1.024000e+03 2.048000e+03
[13] 4.096000e+03 8.192000e+03 1.638400e+04 3.276800e+04
[17] 6.553600e+04 1.310720e+05 2.621440e+05 5.242880e+05
[21] 1.048576e+06 2.097152e+06 4.194304e+06 8.388608e+06
[25] 1.677722e+07 3.355443e+07 6.710886e+07 1.342177e+08
[29] 2.684355e+08 5.368709e+08 1.073742e+09 2.147484e+09
[33] 4.294967e+09 8.589935e+09 1.717987e+10 3.435974e+10
[37] 6.871948e+10 1.374390e+11 2.748779e+11 5.497558e+11
[41] 1.099512e+12 2.199023e+12 4.398047e+12 8.796093e+12
[45] 1.759219e+13 3.518437e+13 7.036874e+13 1.407375e+14
[49] 2.814750e+14 5.629500e+14
[/section] [section title=”Powers of 3″]
> 3^(sequence-1)
[1] 1.000000e+00 3.000000e+00 9.000000e+00 2.700000e+01
[5] 8.100000e+01 2.430000e+02 7.290000e+02 2.187000e+03
[9] 6.561000e+03 1.968300e+04 5.904900e+04 1.771470e+05
[13] 5.314410e+05 1.594323e+06 4.782969e+06 1.434891e+07
[17] 4.304672e+07 1.291402e+08 3.874205e+08 1.162261e+09
[21] 3.486784e+09 1.046035e+10 3.138106e+10 9.414318e+10
[25] 2.824295e+11 8.472886e+11 2.541866e+12 7.625597e+12
[29] 2.287679e+13 6.863038e+13 2.058911e+14 6.176734e+14
[33] 1.853020e+15 5.559061e+15 1.667718e+16 5.003155e+16
[37] 1.500946e+17 4.502839e+17 1.350852e+18 4.052555e+18
[41] 1.215767e+19 3.647300e+19 1.094190e+20 3.282570e+20
[45] 9.847709e+20 2.954313e+21 8.862938e+21 2.658881e+22
[49] 7.976644e+22 2.392993e+23
[/section] [section title=”n squared + 1″]
> sequence^2 + 1
[1]    2    5   10   17   26   37   50   65   82  101  122
[12]  145  170  197  226  257  290  325  362  401  442  485
[23]  530  577  626  677  730  785  842  901  962 1025 1090
[34] 1157 1226 1297 1370 1445 1522 1601 1682 1765 1850 1937
[45] 2026 2117 2210 2305 2402 2501
[/section] [section title=”n cubed”]
> sequence^3
[1]      1      8     27     64    125    216    343    512
[9]    729   1000   1331   1728   2197   2744   3375   4096
[17]   4913   5832   6859   8000   9261  10648  12167  13824
[25]  15625  17576  19683  21952  24389  27000  29791  32768
[33]  35937  39304  42875  46656  50653  54872  59319  64000
[41]  68921  74088  79507  85184  91125  97336 103823 110592
[49] 117649 125000
[/section] [section title=”n multiplied by n minus 1″]

$$n (n – 1)$$

> sequence * (sequence - 1)
[1]    0    2    6   12   20   30   42   56   72   90  110
[12]  132  156  182  210  240  272  306  342  380  420  462
[23]  506  552  600  650  702  756  812  870  930  992 1056
[34] 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892
[45] 1980 2070 2162 2256 2352 2450
[/section] [section title=”2 times n minus 3 divided by 2″]

$${2n – 3} \over {2}$$

> (2*sequence-3)/2
[1] -0.5  0.5  1.5  2.5  3.5  4.5  5.5  6.5  7.5  8.5  9.5
[12] 10.5 11.5 12.5 13.5 14.5 15.5 16.5 17.5 18.5 19.5 20.5
[23] 21.5 22.5 23.5 24.5 25.5 26.5 27.5 28.5 29.5 30.5 31.5
[34] 32.5 33.5 34.5 35.5 36.5 37.5 38.5 39.5 40.5 41.5 42.5
[45] 43.5 44.5 45.5 46.5 47.5 48.5
[/section] [section title=”negative 1 to the power of n”]

$$(-1)^n$$

> (-1)^sequence
[1] -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1
[20]  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1
[39] -1  1 -1  1 -1  1 -1  1 -1  1 -1  1

$$(-1)^{n+1}$$

> (-1)^(sequence+1)
[1]  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1
[20] -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1
[39]  1 -1  1 -1  1 -1  1 -1  1 -1  1 -1
[/section] [section title=”2 times n divided by 2 times n minus 1″]

$${2n} \over {2n – 1}$$

> (2*sequence)/(2*sequence-1)
[1] 2.000000 1.333333 1.200000 1.142857 1.111111 1.090909
[7] 1.076923 1.066667 1.058824 1.052632 1.047619 1.043478
[13] 1.040000 1.037037 1.034483 1.032258 1.030303 1.028571
[19] 1.027027 1.025641 1.024390 1.023256 1.022222 1.021277
[25] 1.020408 1.019608 1.018868 1.018182 1.017544 1.016949
[31] 1.016393 1.015873 1.015385 1.014925 1.014493 1.014085
[37] 1.013699 1.013333 1.012987 1.012658 1.012346 1.012048
[43] 1.011765 1.011494 1.011236 1.010989 1.010753 1.010526
[49] 1.010309 1.010101

This sequence is easier to remember and follow if we look at it in its fractional form:

[/section] [section title=”1 plus negative 1 to the power of n + 1 divided by 2″]

$${1 + (-1)^{n+1}} \over {2}$$

> (1+(-1)^(sequence+1))/2
[1] 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
[30] 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
[/section] [section title=”Fibonacci Sequence”]

$$a_n = \left\{\begin{matrix} 1 \quad & if \; n = 1 \\ a_{n-1}+a_{n-2} \quad &if n > 1 \end{matrix}\right.$$

This is a fun one…first, I write a little function to calculate the nth number in a Fibonacci sequence and then do it for the numbers in sequence.

> fib <- function(n) {a=1; b=1; for(i in 1:n) {t=b; b=a; a=a+t}; a}
> for (i in sequence) { x[i] <- fib(sequence[i])}
> x
[1]           2           3           5           8
[5]          13          21          34          55
[9]          89         144         233         377
[13]         610         987        1597        2584
[17]        4181        6765       10946       17711
[21]       28657       46368       75025      121393
[25]      196418      317811      514229      832040
[29]     1346269     2178309     3524578     5702887
[33]     9227465    14930352    24157817    39088169
[37]    63245986   102334155   165580141   267914296
[41]   433494437   701408733  1134903170  1836311903
[45]  2971215073  4807526976  7778742049 12586269025
[49] 20365011074 32951280099
[/section] [section title=”one divided by 3 to the power of n minus 5″]

$${1} \over {3^{n-5}}$$

> 1/(3^(sequence-5))
[1] 8.100000e+01 2.700000e+01 9.000000e+00 3.000000e+00 1.000000e+00
[6] 3.333333e-01 1.111111e-01 3.703704e-02 1.234568e-02 4.115226e-03
[11] 1.371742e-03 4.572474e-04 1.524158e-04 5.080526e-05 1.693509e-05
[16] 5.645029e-06 1.881676e-06 6.272255e-07 2.090752e-07 6.969172e-08
[21] 2.323057e-08 7.743524e-09 2.581175e-09 8.603916e-10 2.867972e-10
[26] 9.559907e-11 3.186636e-11 1.062212e-11 3.540706e-12 1.180235e-12
[31] 3.934118e-13 1.311373e-13 4.371242e-14 1.457081e-14 4.856936e-15
[36] 1.618979e-15 5.396595e-16 1.798865e-16 5.996217e-17 1.998739e-17
[41] 6.662463e-18 2.220821e-18 7.402737e-19 2.467579e-19 8.225263e-20
[46] 2.741754e-20 9.139181e-21 3.046394e-21 1.015465e-21 3.384882e-22

and fractionally…

[/section] [section title=”Prime Numbers”]
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47
[/section] [section title=”Non-prime Numbers”]
 [1]  0  2  0  4  0  6  0  8  9 10  0 12  0 14 15 16  0 18  0 20 21 22
[23]  0 24 25 26 27 28  0 30  0 32 33 34 35 36  0 38 39 40  0 42  0 44
[45] 45 46  0 48  0 50
[/section] [section title=”Negative 1 to the power of n plus 1 times 2 times n”]

$$(-1)^{n+1} \cdot 2n$$

This produces a sequence of even numbers with numbers alternating between positive and negative values.

> (-1)^(sequence+1)*2*sequence
[1]    2   -4    6   -8   10  -12   14  -16   18  -20   22  -24   26
[14]  -28   30  -32   34  -36   38  -40   42  -44   46  -48   50  -52
[27]   54  -56   58  -60   62  -64   66  -68   70  -72   74  -76   78
[40]  -80   82  -84   86  -88   90  -92   94  -96   98 -100
[/section] [section title=”2/3 to the power of n minus 5″]

$$({2} \over {3})^{n-5}$$

Notice the even and odd progressions in both the numerators and denominators.

[/section] [/sections]

Hope you enjoyed these. Stay tuned for the next part of A Love for Numbers series!

Gian

# The MIT Battlecode Competition Kicks off Today

As some of you already know, there’s a small, sub-genre of computer games called programming games. In these types of games, the main thrust of the primary mechanic is that you must pre-program a robot/tank/entity to do actions and movements and attempt to respond intelligently to any and all threats from other players trying to do the same.

Some of these games required the player to learn a pseudo-assembly language while others operate at a higher level, but most all require the player to program with a toolkit or library that defines and enforces proper gameplay mechanics. There are other restrictions imposed on the player, as well, such as bytecode space restrictions and memory (RAM) restrictions that can cause your bot to be killed if it overflows its allowed space.

Arguably, the biggest and baddest (ie the best, imo) is the AI competition hosted by MIT called 6.370 Battlecode and the bot language is Java. Today, the specs and registrations have opened up for the beginning of the competition. The 6.370 Battlecode competition is open to MIT students as well as non-student general public. If you’re planning on entering or even following the matches, here are a few important dates. See the official website for exact times.

 Registration Opens 1.7.2013 Sprint Tournament 1.16.2013 Seeding Tournament 1.22.2013 Qualifying Tournament 1.29.2013 Final Tournament 2.2.2013

Sites of Interest

Official MIT 6.370 Battlecode website

Official Game Specification Release

# Cogitation Conundrum #2

Ok, here’s the next Cogitation Conundrum for you. It might keep you thinking for a few minutes.

Professor Brainiac, who is getting on in years, is growing absent minded. On the way to a lecture one day, he went through a red light and turned down a one-way street in the wrong direction. A policeman observed the entire scene but did nothing about it. How could Professor Brainiac get away with such behavior?

[spoiler]Professor Brainiac was on foot.[/spoiler]

# Area of Specialty Extra

Every now and then I’ll offer up a teaser that is tailored specifically to certain areas of specialty, mostly biology, biochemistry, math, and logic (because those are my areas of specialty 😛 ). Here’s the first one for you. A microbiologist should get this one.

Arthur the Hunter claimed that, while on an African safari hunting a vicious lion, he slipped and broke his foot. Not to be put off, he managed to continue on long enough to track the lion and kill it. Then he said that while he was at the North Pole during the dead of winter, he caught a terrible cold, but was still able to track and kill a polar bear. Then, to top it off, while in a small boat off the coast of Florida, he was able to catch and land a shark, in spite of the fact that his arm was almost broken. Although Arthur’s tales are hard to believe, on what point do you know he’s lying?

[spoiler]Our friend, Arthur the Hunter was definitely lying when he said he caught a cold while at the North Pole in the dead of winter. One cannot catch a cold in the North Pole in the dead of winter because the temperatures are so low in this part of the world that the common cold virus, Rhinovirus, cannot survive.[/spoiler]