jump to navigation

How to do really fast bit permutations with few operations March 11, 2011

Posted by Michele Fadda in microcontrollers.
add a comment

If you look at the specs of algorithms such as the now semi defunct DES, you are often required to do permutations of bits, i.e. changing the order of bits in a bit field.

One typical example is bit reversal, which comes handy even if you need to switch from little endian to big endian.

But let’s suppose you just need to shuffle bits in a predetermined order. There are lots of WRONG ways of doing this, there are lots of wrong solutions, which will make your program a lot slower than it could be.

Examples of painful slow solutions: use bit masking, use logical AND / OR, bring result into Carry flag, shifts.

If your instruction set allows for direct bit addressing ( e.g.: modern x86 architecture starting with 386 in protected mode), you can gain an about 5x speedup, but that’s not the intelligent way of doing permutations.

The right way:

at compile time:

1) Divide your bit fields in bytes or similar n convenient chunks.

2) build n tables, each of n elements, each element long as the entire bitfield.

3) for each table, each element at the row corresponding to the value of the “chunk” considered as a displacement, should contain “1″ in the permuted destination bits, if the corresponding bits in the original chunk  are themselves set to “1″ and pad to zero everything else.

at run time:

1) divide your bitfields in chunks, for each chunk read the row corresponding to its value in the corresponding table.

2) just OR together the results of the individual array reads.

i.e.: instead of m bit operations, if you need to permute 64 bits you just need 8 indexed reads and 7 OR operations.

That’s a lot better than trying 64 bit masks and shifting results around. Even if you have direct bit addressing, this solution will be 8-10 times faster.

 

Humorous instruction set March 30, 2008

Posted by Michele Fadda in humour, microcontrollers, technology.
Tags: , , , , ,
add a comment
AAC Alter All Commands
AAD Alter All Data
AAO Add And Overflow
AAR Alter At Random
AB Add Backwards
ABR Add Beyond Range
ACQT Advance Clock to Quitting Time
ADB Another Damn Bug [UNIX]
AFF Add Fudge Factor
AFHB Align Fullword on Halfword Boundary
AFP Abnormalized Floating Point
AFVC Add Finagle’s Variable Constant
AGB Add GarBage
AI Add Improper
AIB Attack Innocent Bystander
AMM Answer My Mail
AOI Annoy Operator Immediate
AR Alter Reality
ARN Add and Reset to Non-zero
ARZ Add and Reset to Zero
AS Add Sideways
AT Accumulate Trivia
AWP Argue With Programmer
AWTT Assemble With Tinker Toys
BAC Branch to Alpha Centauri
BAF Blow All Fuses
BAH Branch And Hang
BALC Branch And Link Cheeseburger
BAW Bells And Whistles
BB Branch on Bug
BBBB Byte Baudy Bit and Branch
BBI Branch on Burned-out Indicator
BBL Branch on Burned-out Lamp
BBLB Branch on Blinking Light Bulb
BCB Burp and Clear Bytes
BCF Branch on Chip box Full
BCIL Branch Creating Infinite Loop
BCR Backspace Card Reader
BCU Be Cruel and Unusual
BD Backspace Disk
BD Branch to Data
BDC Break Down and Cry
BDM Branch and Disconnect Memory
BDT Burn Data Tree [next opcode after decorate data tree]
BE Branch Everywhere [As in HHGttG's Infinite Improbability Computer]
BF Belch Fire
BH Branch and Hang
BLC Branch and Loop Continuous
BLI branch and loop infinite
BLM Branch, Like, Maybe
BLMWM Branch, Like, Maybe, wow, Man
BLP Boot from Line Printer
BLR Branch and Lose Return
BM Branch Maybe
BMI Branch on Missing Index
BMP Branch and Make Popcorn
BNA Branch to Nonexistent Address
BNR Branch for No Reason
BOD Branch on Operator Desperate
BOOP Boot Operator
BYOP Byte Operator
BPB Branch on Program Bug
BPD Branch on Programmer Debugging
BPIM Bury Programmer In Manuals
BPO Branch on Power Off
BR Byte and Run
BRA Branch to Random Address
BRI BRanch Indefinitely
BRL BRanch and Leak
BRO BRanch to Oblivion
BRT BRanch on Tuesdays
BSC Burst Selector Channel
BSI Backup Sewer Immediate
BSM Branch and Scramble Memory
BSO Branch on Sleepy Operator
BSST BackSpace and Stretch Tape
BTD Byte The Dust
BTJ Branch and Turn Japanese
BTO Branch To Oblivion
BW Branch on Whim
BWABL Bells, Whistles and Blinking Lights
BWOP BeWilder Operator
CAF Convert Ascii to Farsic
CAI Corrupt Accounting Information
CAIL Crash After I Leave
CAT Confused And Tired [UNIX]
CBA Compare and Branch Anyway
CBNC Close, But No Cigar
CBS Clobber BootStrap
CC Call Calvary
CC Crappy Control [UNIX]
CCB Chocolate Chip Byte-mode
CCB Consult Crystal Ball
CCCI Clear Condition-Codes Indefinitely
CCD Choke, Cough and Die
CCD Clear Current Directory [this may really exist!]
CCD Clear Core and Dump
CCR Change Channels Random
CCS Chinese Character Set
CCWR Change Color of Write Ring
CDR Complement Disk Randomly
CFS Corrupt File Structure
CG Convert to Garbage
CH Create Havoc
CHAPMR CHAse Pointers around Machine Room
CIB Change Important Byte
CIMM Create Imaginary Memory Map
CM Circulate Memory
CMD Compare Meaningless Data
CMD CPU Melt Down
CMI Clobber Monitor Immediately
CML Compute Meaning of Life
CMP Create Memory Prosthesis
CMS Click MicroSwitch
CN Compare Nonsensically
CNB Cause Nervous Breakdown
COLB Crash for Operator’s Lunch Break
COMF COMe From
COS Copy Object Code to Source File
COWHU Come Out With your Hands Up
CP%FKM CPU – Flakeout mode
CP%WM CPU – Weird Mode
CPB Create Program Bug
CPR Compliment PRogrammer(“Aren’t you cute!”)
CRASH Continue Running After Stop or Halt
CRM Clear Random Memory
CRN convert to Roman numerals
CRYPT reCuRsive encrYPt Tape mnemonic [UNIX]
CS Crash System
CSL Curse and Swear Loudly
CSN Call Supervisor Names
CSNIO Crash System on Next I/O
CSU Call Self Unconditional [the ultimate in recursive programming]
CSYS Crash SYStem
CTDMR Change Tape Density, Mid Record
CUC Cheat Until Caught
CVFL Convert Floating to Logical
CVFP ConVert FORTRAN to PASCAL
CVG ConVert to Garbage
CWAH Create Woman And Hold
CWDC Cut Wires and Drop Cores
DA Develop Amnesia
DAO divide and overflow
DAP De-select Active Peripheral
DAUF Delete All Useless Files [would YOU trust a computer that far?]
DBL Desegregate Bus Lines
DBR Debase Register
DBZ Divide By Zero
DC Degauss Core
DC Divide and Conquer
DCAD Dump Core And Die
DCD Drop Cards Double
DCGC Dump Confusing Garbage to Console
DCI Disk Crash Immediate
DCON Disable CONsole
DCT Drop Cards Triple
DCWPDGD Drink Coffee, Write Program, Debug, Get Drunk
DD Destroy Disk
DDC Dally During Calculations
DDOA Drop Dead On Answer
DDS Delaminate Disk Surface
DEB Disk Eject Both
DEC Decompile Executable Code
DEI Disk Eject Immediate
DEM Disk Eject Memory
DES Disk Eject Swapped
DHTPL Disk Head Three Point Landing
DIA Develop Ineffective Address
DIE DIsable Everyting (UN?X during hardware errors? :-) )
DIIL Disable Interrupts and enter Infinite Loop
DIRFW Do It Right For Once
DISC DISmount CPU
DK Destroy Klingons
DK%WMM Disk Unit – Washing Machine Mode
DKP Disavow Knowledge of Programmer
DLN Don’t Look Now…
DLP Drain Literal Pool
DMPE Decide to Major in Physical Education
DMPK Destroy Memory Protect Key
DO Divide and Overflow
DOC Drive Operator Crazy
DPC Decrement Program Counter
DPK Destroy storage Protect Key
DPMI Declare Programmer Mentally Incompetent
DPR Destroy Program
DPS Disable Power Supply
DRAF DRAw Flowchart
DRI Disable Random Interrupt
DRT Disconnect Random Terminal
DS Deadlock System
DSH Destroy Sector Header
DSI Do Something Interesting
DSPK Destroy Storage Protect Key
DSR Detonate Status register
DSTD Do Something Totally Different
DSUIT Do Something Utterly, Indescribably Terrible
DT%FFP DecTape – Unload and Flappa-Flap
DT%SHO DecTape – Spin Hubs Opposite
DTC Destroy This Command
DTI Do The Impossible
DTRT Do The Right Thing
DTVFL Destroy Third Variable From Left
DU Dump User
DUD Do Until Dead
DW Destroy Work
DW Destroy World
DWIM Do What I Mean
DWIT Do What I’m Thinking
EAL Enable AC to Logic rack
EAO Enable AC to Operator
EBRS Emit Burnt Resistor Smell
EC Eject Carriage
ECL Early Care Lace
ECO Electrocute Computer Operator
ECP Erase Card Punch
ED Eject Disk
ED Execute Data
ED Expunge Data [UNIX]
ED Eject Disk
EDD Eat Disk and Die
EDIT Erase Data and Increment Time
EDR Execute Destructive Read
EDS Execute Data Segment
EEP Erase Entire Program
EFD Eject Floppy Disk
EIAO Execute In Any Order
EIO Erase I/O page
EIOC Execute Invalid OP Code
EJD d,v Eject disk in drive d with initial velocity v
EJD%V EJect Disk with initial velocity V
ELP Enter Loop Permanently
EM Evacuate Memory
EMSL Entire Memory Shift Left
EMT Electrocute Maintenance Technician
ENA ENable Anything
ENF Emit Noxious Fumes
EO Electrocute Operator
EOB Execute Operator and Branch
EOI Execute Operator Immediate [a fast version of another instruction]
EP Execute Programmer
EPI Execute Programmer Immediate
EPP Eject Printer Paper
EPS Electrostatic Print and Smear
EPS Execute Program Sideways
EPT Erase Process Table
EPT Erase Punched Tape
ERIC Eject Random Integrated Circuit
ERM Erase Reserved Memory
EROM Erase Read Only Memory
EROS Erase Read Only Storage [Sounds like an IBM special!]
ERS erase read-only storage
ESB Eject Selectric Ball [from IBM selectric typewriter terminals]
ESL Exceed Speed of Light
ESP Enable SPrinkler system
ETI Execute This Instruction [for recursive programs]
ETM Emulate Trinary Machine
EVC Execute Verbal Commands
EWD Execute Warp Drive
EXX [A real instruction on the Zilog Z-80 -- Zilog is owned by EXXon]
FB Find Bugs
FCJ Feed Card and Jam
FDR Fill Disk Randomly
FFF Form Feed Forever
FLD FLing Disc
FLI Flash Lights Impressively
FM Forget Memory
FMP Finish My Program
FOPC [Set] False Out-of-paper Condition
FPC Feed Paper Continuously
FPT Fire Photon Torpedoes
FRG Fill with Random Garbage
FSM Fold, Spindle, and Mutilate
FSRA Forms Skip and Run Away
GBB Go to Back of Bus
GCAR Get Correct Answer Regardless
GDP Grin Defiantly at Programmer
GDR Grab Degree and Run
GENT GENerate Thesis
GEW{JO} Go to the End of the World {Jump Off}
GIE Generate Irreversible Error
GLC Generate Lewd Comment
GMC Generate Machine Check
GMCC Generate Machine Check and Cash
GND Guess at Next Digit
GORS GO Real Slow
GREM Generate Random Error Message
GREP Global Ruin, Expiration and Purgation [UNIX]
GRMC Generate Rubber Machine Check
GS Get Strange [randomly inverts bits fed to the instruction decoder]
GSB Gulp and Store Bytes
GSI Generate Spurious Interrupts
GSU Geometric Shift Up
HAH Halt And Hang
HCF Halt and Catch Fire
HCP Hide Central Processor [makes virtual CPU's act like virtual memories]
HCRS Hang in Critical Section
HDO Halt and Disable Operator
HDRW Halt and Display Random Word
HELP Type “No help available”
HF Hide a File
HGD Halt, Get Drunk
HHB Halt and Hang Bus
HIS Halt in Impossible State
HOO Hide Operator’s Output
HRPR Hang up and Ruin Printer Ribbon
HUAL Halt Until After Lunch
IAND Illogical And
IBR Insert Bugs at Random
ICB Interrupt, crash and burn
ICM Immerse Central Memory
ICMD Initiate Core Melt-Down
ICSP Invert CRT Screen Picture
IDC Initiate Destruct Command
IDI Invoke Divine Intervention
IDPS Ignore Disk Protect Switch
IEOF Ignore End Of File
IF Invoke Force
IGI Increment Grade Immediately
IGIT Increment Grade Immediately Twice
II Inquire and Ignore
IIB Ignore Inquiry and Branch
IIB Ignore Interrupt and Branch
IIC Insert Invisible Characters
IIL Irreversable Infinite Loop
IM Imagine Memory
IMPG IMPress Girlfriend
INCAM INCrement Arbitrary Memory location
INOP Indirect No-op
IOI Ignore Operator’s Instruction
IOP Interrupt processor, Order Pizza
IOR Illogical OR
IP Increment and Pray
IPS Incinerate Power Supply
IPS Increment Processor Status
IPT Ignite Paper Tape
IRB Invert Record and Branch
IRC Insert Random Commands
IRE Insert Random Errors
IRPF Infinite Recursive Page Fault
ISC Ignore Supervisor Calls
ISC Insert Sarcastic Comments
ISI Increment and Skip on Infinity
ISP Increment and Skip on Pi
ITML Initiate Termites into Macro Library
IU Ignore User
JAA Jump Almost Always
JFM Jump on Full Moon
JHRB Jump to H&R Block
JLP Jump and Lose Pointer
JMAT JuMp on Alternate Thursdays
JNL Jump when programmer is Not Looking
JOM Jump Over Moon
JRAN Jump RANdom [not to be confused with IRAN - Idiots random]
JRCF Jump Relative and Catch Fire
JRGA Jump Relative and Get Arrested
JRN Jump RaNdom
JRSR Jump to Random Subroutine
JSU Jump Self Unconditional [the ultimate in iterative programming]
JT Jump if Tuesday
JTZ Jump to Twilight Zone
JWN Jump When Necessary
KUD Kill User’s data
LAGW Load And Go Wrong
LAP Laugh At Program(mer)
LCC Load and Clear Core
LCD Load and Clear Disk
LCK Lock Console Keyswitch
LEB Link Edit Backwards
LIA Load Ineffective Address
LMB Lose Message and Branch
LMO Load and Mug Operator
LMYB Logical MaYBe
LN Lose inode Number [UNIX]
LOSM Log Off System Manager
LP%PAS Line Printer – Print And Smear
LP%RDD Line Printer – Reverse Drum Direction
LP%TCR Line Printer – Tangle and Chew Ribbon
LPA Lead Programmer Astray
LRD Load Random Data
LSBL Lose Super BLock [UNIX only]
LUM LUbricate Memory
LWM Load Write-only Memory
MAB Melt Address Bus
MAN Make Animal Noises
MAZ Multiply Answer by Zero
MBC Make Batch Confetti
MBH Memory Bank Hold-up
MBTD Mount Beatles on Tape Drive
MBTOL Move Bugs to Operator’s Lunch
MC Move Continuous
MD Move Devious
MDB Move and Drop Bits
MDDHAF Make Disk Drive Hop Across Floor [Stevans's favorite (he made it up)]
MLP Multiply and Lose Precision
MLR Memory Left Shift and Branch
MLR Move and Lose Record
MLSB Memory Left Shift and Branch
MMLG Make Me Look Good
MNI Misread Next Instruction
MOP Modify Operator’s Personality
MOU MOunt User [causes computer to screw you once again]
MPLP Make Pretty Light Pattern
MSGD Make Screen Go Dim
MSIP Make Sure Plugged In
MSR Melt Special Register
MT%HRDV MagTape – High speed Rewind and Drop Vacuum
MTI Make Tape Invalid
MW Malfunction Whenever
MWC Move and Wrap Core
MWK multiply work
MWT Malfunction Without Telling
NTGH Not Tonight, I’ve Got a Headache
OCF Open Circular File
OML Obey Murphy’s Laws
OPP Order Pizza for Programmer
OSI Overflow Stack Indefinitely
OTL Out To Lunch
PAS Print And Smear
PAUD PAUse Dramatically
PAZ Pack Alpha Zone
PBC Print and Break Chain
PBD Print and Break Drum
PBM Pop Bubble Memory
PBPBPBP Place Backup in Plain Brown Paper Bag, Please [for stealing code]
PBST Play Batch mode Star Trek
PCI Pleat Cards Immediate
PCR Print and Cut Ribbon
PD Punch Disk
PEHC Punch Extra Holes in Cards
PFE Print Floating Eye [Roguers look out!]
PFML Print Four Million Lines
PI Punch Invalid
PIBM Pretend to be an IBM
PIC Print Illegible Characters
PIC Punch Invalid Character
PNRP Print Nasty replies to Programmer
PO Punch Operator
POFF Power Off
PON Power On
POPN Punch OPerator’s Nose
PPA Print Paper Airplanes
PPL Perform Perpetual Loop
PPP Print Programmer’s Picture
PPSW Pack Program Status Word
PRS Print And Smear
PSP Print and Shred Paper
PSR Print and Shred Ribbon
QWA Quit While Ahead
RA Randomize Answer
RAM Reorganize and Abort Monitor
RASC Read And Shred Card
RAST Read and Shred Tape
RAST Rewind And Stretch Tape
RAU Ridicule All Users
RBA Random Branch Anywhere
RBAO Ring Bell and Annoy Operator
RBG Random Bug Generate
RBLY Restore Backup from Last Year
RBT Read and Break Tape
RBT Read Blank Tape
RBT Rewind and Break Tape
RCAJ Read Card And Jam
RCB Read Commands Backwards
RCB Run Clock Backwards
RCC Read Card and Chew
RCCP Randomly Corrupt Current Process
RCF Rewind Cabinet Fans
RCKG Read Count Key and Garbage
RCR Rewind Card Reader
RCRV Randomly Convert to Reverse Video
RCSD Read Card and Scramble Data
RD Randomize Data
RDA Refuse to Disclose Answer
RDD Reverse Disk Drive
RDF Randomize Directory Filenames
RDI Reverse Disk Immediate
RENVR Rename Variables Randomly
RET Read and Erase Tape
RIC Rotate Illogical thru Carry
RID Read Invalid Data
RIR Read Invalid Record
RIRG Read Inter-Record Gap
RIRG Rewrite Inter-Record Gap [random replacement of similar mnemonic]
RLC Re-read last card
RLC Relocate and Lose Core
RLI Rotate Left Indefinitely
RLP Refill Light Pen
RLP Rewind Line Printer
RM Ruin My files [UNIX]
RMI Randomize Memory Immediate
RMV Remove Memory Virtues
RN Read Noise
RNBS Reflect Next Bus Signal
RNR Read Noise Record
ROD ROtate Diagonally
ROM Read Operator’s Mind
ROOP Run Out Of Paper
ROPF Read Other People’s Files
ROS Reject Op System
ROS Return On Shield
ROT Rotate Disk [fixes broken drives]
RP Read Printer
RPB Raise Parity Bits
RPBR Reverse Parity and BRanch
RPC Randomize Program Counter
RPM Read Programmer’s Mind
RPU Read character and Print Upside down
RRB Read Record and Blush
RRC Rotate Random thru Carry
RRR Read Record and Run away
RRRL Random Rotate Register Left
RRSG Round and Round She Goes…
RRSGWSSNK Round and Round She Goes, Where She Stops, Nobody Knows
RRT record and rip tape
RS Random Slew
RSD Read and Scramble Data
RST Rewind and Stretch Tape
RT Reduce Throughput
RT Reverse Throughput
RTS Return To Sender
RWD rewind disk
RWS Return With Shield
SAD Seek And Destroy
SAI Skip All Instructions
SAS Sit And Spin
SC Scramble Channels
SC Shred Cards
SCB Spindle Card and Belch
SCCA Short Circuit on Correct Answer
SCH Slit Cards Horizontal
SCI Shred Cards Immediate
SCOM Set Cobol-Only Mode
SCRRC SCRamble Register Contents
SCST Switch Channel to Star Trek
SCTR Stick Card To Reader
SD Scramble Directory
SD Slip Disk
SDC Spool Disk to Console
SDDB Snap Disk Drive Belt
SDE Solve Differential Equations
SDI Self Destruct Immediately
SEB Stop Eating and Burp
SEX Set EXecution register [a real instruction for the RCA 1802]
SEX Sign EXtend
SFH Set Flags to Half mast
SFT Stall For Time
SFTT Strip Form Tractor Teeth
SHB Stop and Hang Bus
SHCD SHuffle Card Deck
SHIT Stop Here If Thursday
SHON Simulate HONeywell CPU [permanent NO-OP]
SHRC SHRed Card
SHRT SHRed Tape
SID Switch to Infinite Density
SLP Sharpen Light Pencil
SMC Scramble memory contents
SMD Spontaneous Memory Dump (Use only with classified data)
SMS Shred Mylar Surface
SMT Stretch MagTape
SNM Show No Mercy
SOAWP SOlve All the World’s Problems
SOB [a real PDP-11 instruction]
SOD Surrender Or Die!
SOP Stop and Order Pizza
SOS Sign Off, Stupid
SP Scatter Print
SPA Sliding Point Arithmetic
SPS Smoke Power Supply
SPSW Scramble Program Status Word
SRBO Set Random Bits to Ones
SRBZ Set Random Bits to Zeroes
SRC Skip to Random Channel
SRCC Select Reader and Chew Cards
SRD Switch to Random Density
SRDR Shift Right, Double Ridiculous
SRO Sort with Random Ordering
SRR Set Registers to Random values [usually used prior to a RET or RTS]
SRR Shift Registers Random
SRSD Seek Record and Scratch Disk
SRU Signoff Random User
SRZ Subtract and Reset to Zero
SSB Scramble Status Byte
SSD Seek and Score Disk [good for testing]
SSD Stacker Select Disk
SSJ Select Stacker and Jam
SSJP Select Stacker and Jump
SSM Solve by Supernatural Means
SSM Stacker Select Memory
SSP Smoke and SPark
SSP Seek SPindle
SST Stop and Stretch Tape
ST Set and Test
STD Stop, take drugs
STPR SToP Rain
STTHB Set Terminal to Three Hundred Baud
SUI Subtract User’s IQ
SUME Surprise Me
SUP Solve Unsolvable Problem
SUR Screw Up Royally
SUS Stop Until Spring
SUS Subract Until Senseless
SWAT SWAp Terminals
SWN SWap Nibbles
SWOS SWap out Operating System
SWS Sort to Wrong Slots
SWT Select Wrong Terminal
SZD Switch to Zero Density
TARC Take Arithmatic Review Course
TBFTG Two Burgers and Fries To Go
TDB Transfer and Drop Bits
TDS Trash Data Segment
TLNF Teach me a Lesson I’ll Never Forget
TLO Turn indicator Lights Off
TLW Transfer and Lose Way
TN Take a Nap
TOG Time Out, Graduate
TOH Take Operator Hostage
TOO Turn On/Off operator
TOS Trash Operating System
TPD Triple Pack Decimal
TPDH Tell Programmer to Do it Him/Her self
TPN Turn Power On
TPO Turn Power Off
TPR Tear PapeR
TR Turn into Rubbish [UNIX]
TRA Te Rdls Arvs [Type Ridiculous Abbreviations]
TSH Trap Secretary and Halt
TSM Trap Secretary and Mount
TST Trash System Tracks
TT%CNK TeleType – Clunk Noise
TT%EKB TeleType – Electrify KeyBoard
TTA Try, Try Again
TTITT Turn 2400 foot tape Into Two 1200 foot tapes
TTL Time To Log off
UAI Use Alternate Instruction set
UCB Uncouple Communication lines and Break
UCK Unlock Console Keyswitch
UCPUB Uncouple CPU and Branch
UDR Update and Delete Record
UMR Unlock Machine Room
UOP Useless Operation
UP Understand Program
UTF Unwind Tape onto Floor
UUBR Use Undefined Base Register
VAX Violate All executions
VFE Violate Field Engineer
VFO Violate Female Operator
VMA Violate Maintenance Agreement
VNO Violate Noise Ordinance
VPA Vanishing Point Arithmetic
VVM Vaporise Virtual Memory
WAD Walk Away in Disgust
WC Waste Core [UNIX]
WCR Write to Card Reader
WED write and erase data
WGPB Write Garbage in Process-control Block
WHP Wave Hands over Problem
WI Why Immediate
WID Write Invalid Data
WNHR Write New Hit Record
WNR Write Noise Record
WPET Write Past End of Tape
WSE Write Stack Everywhere
WSWW Work in Strange and Wonderous Ways
WUPO Wad Up Printer Output
WWLR Write Wrong Length Record
WWR Write Wrong Record
XIO Execute Invalid Op code
XKF Execute Kermit the Frog
XMB Exclusive MayBe
XOH Execute no-Op and Hang
XOR Execute OperatoR
XOS Exchange Operator’s Sex
XPR Execute Programmer
XVF Exchange Virtue for Fun
YKWIM You Know What I Mean
ZAP Zero and Add Packed
ZD Zap Directory
ZPI ZaP Immediate

Explaining the Cypress PSOC Choice March 29, 2008

Posted by Michele Fadda in microcontrollers, PSOC, technology.
Tags: , , , ,
add a comment

Explaining the PSOC Choice.
PSOC is an acronym that stands for “Programmable System On a Chip”, and that, as often happens in the world of electronics, indicates substantially different devices, compared with the seemingly similar acronyms SOC “System On a Chip”, which point at highly integrated digital components, but usually lacking analog modules.
PSOC is, unlike the generic acronym SOC, a product of the American company Cypress Semiconductors, and integrates both analog and digital subcomponents on the same chip. Often PSOC are called “mixed signal matrix” because they are programmable arrays, where the signals are processed at the same time in analog and digital form. 
This far, we have just touched the boring subject of taxonomy nomenclature of a peculiar subtype of electronic devices, which apparently does not mean a lot.

PSOC is important, and in some ways even revolutionary, as it changes for good the way we design and make electronic appliances, in ways that are of paramount importance for a small company, as they offer opportunities to improve its competitiveness.
In a PSOC we find a number of modules, which are user configurable by writing into registers. These modules can be interconnected with one another through internal busses. These programmable modules, depending on their programming, actually “become” a peripheral device. E.g. depending on how they are programmed they can become an amplifier or a programmable filter, while more complex devices are  obtained by combining with several modules. For instance, a digital analog converter can be obtained by combining together an analog comparator, a programmable voltage generator (DAC) and a counter or a decimator. A simplification of the operation of a digital converter can be rapidly summarised as follows: The counter scans the range of binary values, the programmable voltage generator converts each of them into a voltage, while the comparator indicates which of the values generated corresponds to the voltage to be measured. Of course, many more possible types of analog-digital converters are possible, each using different techniques and approaches, depending on the accuracy and speed required, and which “consume” more or fewer modules available. This means that you can implement different resolutions and different sampling techniques. All this is done “automagically” by Cypress development software. If we need a measuring amplifier or a filter to condition the signal, we can place and program that too along the signal chain. This way of working is in sharp contrast to what happens with virtually all other traditional microcontrollers. With traditional microcontrollers, if at some point, we realize that there aren’t enough bits of resolution in the ADC, or that its sampling frequency is wrong, it is almost always necessary to go back to the drawing board, select another component, maybe belonging the same family, but whose peripheral programming will be different. To add insult to injury, the pins devoted to analog signals are almost certainly mapped differently and cannot be “moved around”. If we had printed circuit boards designed, this means we have to have then redone from scratch, and we have to rewrite the firmware as well.

With PSOC, we can decide whether we need converters between 6 and 14 bits, based on different principles of operation, and we can deploy them on the same component. We can reroute pins to our heart content. Similarly, you can have PWMs and digital timers: Will four 8-bit do or is it better to have one 32-bit counter? The designer can choose, and will have to deal with tradeoffs, as there is a finite number of elementary digital modules in a PSOC. However, this is a true revolution in terms of designer freedom.
The PSOC can even be reconfigured on the run, e.g. if a PSOC is used in a transceiver, it is possible to implement the functions of a radio receiver when a “push to talk” button is released. When you press the “push-to talk”, it is possible to reconfigurare the radio as a transmitter, using the same hardware. Cypress  marketing indicates this feature with the slogan “Use 400% of your resources.” As always, Marketing is pushing things a little, since this feature is practically limited by reaction time, computing power, memory on board, which makes “200%” a target not always easy to achieve. 
This seems all very complicated… Indeed it is, but the beauty of this approach is that all the configuration activity does not take place ”by hand” insertion of binary codes inside registers, but rather through a visual tool: “pseudocomponents” that implement functions are choosen from a palette, while you can browse their characteristics from the instantly recallable datasheet.

The development system automatically generates the configuration and initialization, which the designer usually has no need to worry about. For example, the design software can then automatically convert projects based on a given PSOC to another. 
Cypress offers two development environments, PSOC Express, which is used for rapid prototyping and that does not require knowledge of programming languages, and one for the design of “production level” projects, PSOC Designer, which allows fine control by means of C and assembler programming.

I must admit being initially very skeptical about PSOC Express, as designer: I was not convinced a “generator applications” could produce anything remotely viable. Actually PSOC Express, although not very intuitive, is indeed really easy to use and readilt implements almost everything needed, thanks to a “visual syntax” that allows the designer to draw from concepts such as priority encoders, tables decoding , finite state machines, delays. Express works at a more abstract level than “writing code”. PSOC Express moves into the realm of entity-level application, an object-oriented and visual way. For example, an accelerometer in PSOC express, including data acquisition and signal conditioning is represented as a visual “component”, as is a an USB interface. I have personally witnessed that is actually possible to build a software test, and verifying a hardware system in a few tens of minutes. A dear friend and fellow designer became tangle in a mess, trying to solve a problem equivalent to the one that I faced, which I solved in a few days. The difference between the two designers? I had at my disposal a set of high-level APIs and the ability to perform experiments and validate approaches in a few minutes, while he was forced to bang bits into registers in C and Assembler.

The last time I heard from him, he did not know yet if his trouble was at hardware or software level.  
After quickly building a conceptual prototype with PSOC Express, having determined that there are no macroscopic errors , it is possible to refine a project with PSOC Designer. With PSOC Designer it is possible to achieve a complete control at device-level in C ad Assembler, and have circuit emulation. But at this stage we are already certain that all the basic pieces of the puzzle fit together, and we can progress at speed. 
In each of the two development systems, most of the complexity of the project is handled automatically by a visual tool. If needed, the designer can intervene at a very low level, even modifying projects initially developed in Express, with PSOC Designer.

This approach is a huge innovation in a field where very little has changed during the last thirty years.

We can say with good confidence that there are no competing products with the same characteristics. In particular, anyone who has tried to convert a project developed for the same family (say 8051) on a similar core, and can use only traditional tools, knows this can become a nightmare. Doing this “automatically” sounds very sci-fi.  With PSOC tools this is not just a dream but a daily reality, which usually results in automatic translation of mapping between devices, often in matter of a few minutes.
It seems to be back to the times of general electronic kits on breadboards, which provided a number of components, which we could freely interconnect, giving free room to our imagination.  PSOC is really a general purpose kit on a chip. In only a few square millimeters of space it contains a large number of complex programmable and controllable from a digitally microcontroller. 
In terms of computing power MIPS, I admit that speed and computing power is not the main selling point in the current PSOC breed. PSOC performance is comparable to a good 8-bit microcontroller, but not to an exceptional one: clock goes up to 24 MHz, but with instructions often taking many clock cycles and having very few registers (four: status, accumulator, index, stack). Cypress announced almost a year ago that the evolution of the current PSOC will be based on two new cores, one based on a 8051 core and a more powerful based on ARM.
For the moment being, while we wait for more powerful versions, PSOC business is definitely not processing power at high-speed, but is rather reduction of PCB real estate and cheap, low count BOMs.
PSOC do not have a low unit cost, compared to otherseemingly cheaper solutions. However the cost of a PSOC based  project is nonetheless often less expensive: Their advantage in logistics terms is the huge reduction in stocks of different parts, as well as the need for fewer external connections, fewer components and hence greater reliability. It is useful to remember that, potentially, every single welding spot can introduce a fault. A component that allows you to have an subsystem integrated on a chip breaks down, statistically speaking,  a lot less often. Moreover, it is not rare to be able to cut down the number of components by 50 or 60%, as well as the physical dimensions of the system.

With a PSOC we rarely need to to place components such as a crystals, resistors and capacitors. Passive components are often just an optional extra.
PSOC are currently used in many successful innovative products, in particular, CAPSENSE technology, replace buttons and knobs with capacitive sensors sensitive to the touch. Capsens is employed widely in consumer appliances such as, white goods, phones, mp3 players. Cypress’ Capsense  is based on a sophisticated delta modulation , driven by a pseudorandom oscillator, which allows for high sensitivity, noise immunity, the ability to adapt to environment temperature, and to operate in adverse conditions such as rain.
For a small or medium enterprise this mean that PSOC can enable tackling technological projects, with the certainty of reaching a result, thanks to a powerful and reliable development environment. PSOC introduce the ability of modifying and reconfiguring almost all aspects of the project at low cost: We are no longer limited to peripherals mapped to fixed positions, tied to the specific pins. In case of a mistake, it is almost always possible to reconfigure and correct it without redoinf printed circuit boards and having to restart from from scratch each time. 
Thus the project risk, and initial investment decreases significantly, as does “time to market”, which is always critical in how it allows to distance (or pursue) competition. To some extent, it is possible to update a product at hardware level, involving the analog part, after it was delivered to the customer.

Cypress Express 3.0 for Cypress PSOC, I’m a convert! March 14, 2008

Posted by Michele Fadda in microcontrollers, PSOC, technology.
Tags: , , , , , , , , ,
add a comment

I must admit that, being an old timer, I had considered that software tool with loads of suspicion.

“No coding necessary” probably triggered some nerdish response of mine, a shrug full of contempt, close to “I very much doubt a thing can write code better than I” …

Well, I eventually found out what Express is all about.

Cypress Express is an excellent tool when it comes to blazingly fast prototyping.

It is true that it cannot beat me or any pro in generating optimised and finely hand optimised, tuned code.

However where this exceptional application really shines is testing hardware, with proven projects, in less time you can say 1 2 3 (wait, no, just a little bit longer than that).

I have a friend who, a few weeks ago, kept complaining that he was late, had to work during week ends because of a problem with a I2C bus interface, having forgotten that some bit had changed address from one release of a datasheet and another belonging to newer silicon.

Well, sure as hell he is not using, contrary to my suggestions, Cypress! He is using another vendor which does not provide a confortable and practical API, and tools which make programming I2C a dependable and quick activity.

He has been toiling with that thing for about a month, and my friend ended up becoming even less amiable than he usually is. I had to double check whether a system I am designing talks on I2C bus properly, and I wrote and tested both sides of the communication in less than one hour, and it took me so long because I like to keep a relaxed approach and proceed methodically, with order.

I had prepared a logiscope, ready at hand, and I found out I was not going to need it to debug anything, because everything worked, just fine, at first attempt. I was almost disappointed: gee, this thing is keeping me from getting all the fun! Anyway, I don’t know if it is even worth posting this small, but useful I2C bus monitor on this blog, as the application is so easy that it is trivial:

In Express you just need to place on the canvas the icons of I2C slave interface, a valuator, the icon of a LCD panel. You then fill in properties (I2C address being the most important), edit the transfer function (which is something like “if 1 then Display=I2C_value). You assign pins, and program the unit.

That’s all, finished, presto! Building a radio remote control with PSOC wUSB is not nearly more complex than that: a working prototype is something you can assemble on Cypress evaluation boards in less than 15 minutes, from scratch.

Cypress PSOC USB in a nutshell March 14, 2008

Posted by Michele Fadda in microcontrollers, PSOC, technology.
Tags: , , , ,
add a comment

Cypress PSOC USB are present on some members of the PSOC family, eg on 24000, which is the only chip containing practically all the PSOC capabilities: digital/analog mixed signal matrix, capsense, USB.

PSOC USB has some limitation. It is true that PSOC implement USB 2.0, but only with a maximum speed of 12 Mb/sec. This is not USB 1.1, as you can be 2.0 compliant, but still unable to go faster than what in USB trade jargon is called “high speed”, that is 12 Megabyte per second.

All you can have is 4 access points plus the control access point, i.e.: as all access point besides the mandatory control point in monodirectional you can have 2 upstrem and 2 downstream, or any combination of 4. The buffers cannot be longer than 1K, and be warned that the PSOC is not a very fast microcontroller either.

A Cypress FAE recommendes sticking to approaches not involving the need for the development of a custom driver. As maximum speed is 12 Mb/sec this approach is viable, as it may involve the development of either a HID based project or USB com emulation, rather than custom driver development, which tends to verge on the really expensive very quickly. A HID (human interface device) does not need a driver as it is part of core Windows driver, and work with ANY versions of Windows, so, no angry calls to support are to be expected.

HID interfaces have recently achieved a speed capability of 12 Mb/sec. previously, this approach was limited to 64K/sec, which is however more than enough for most simple controls, but is not sufficient for those needing bulk data transfers or streaming.

So, PSOCs do not offer all USB 2.0 has to offer, but are a quickpath in getting things done, if your needs don’t involve streaming video in real time or any application requiring a throughput of 480 Mb/sec.

They are simple, and tools are generosly provided by Cypress which simplify the design of HID devices, these tools, with other vendors you either don’t have, or have to pay for. If you want to achieve 480 Mb/sec transfers, other, more specific Cypress components exist which are better suited for the job.

Cypress PSOC, even in USB never really shines in anything but integration: it is a small component which contains an amazing lot of possibilities, e.g.: you can sample a capacitive keyboard, sample and filter a voltage, connect to a wireless radio, drive I2c bus devices, and have USB, all in one chip.

This is a feat no Cypress competitor, at the current state of the art, can claim being able to achieve.

These components have been studied in order to reduce BOM: even the pullup resistors needed by the interface are integrated, because havint to add them externally would involve a more complexity and cost.

(more…)

Parallel data processing/computations – do we need them? March 4, 2008

Posted by Michele Fadda in technology.
Tags: , , , , ,
add a comment

This is not about scientific grid systems but rather commercial and open source ones.
Basically there are some open source tools that allows to process data/execute CPU consuming tasks in parallel but the question about their usage. Do we need these kind of software or it’s better to solve it on hardware level?

In my view, which is widely shared in the industry, we always need whatever added speed technology is going to afford.

On software being better than hardware, on this issue, I would consider the following: Do you need a real time response, on a local machine?

If you need a very fast response, i.e.: milliseconds on a heavily computational task, but not a hugely massive one, specialised hardware will always win because you won’t need to propagate and collect intermediate results on a network.

In particular, nowadays we are beginning to have flexibly reprogrammable hardware: FPGAs are currently being used as processing nodes in current supercomputers, together with more traditional CISC processors (e.g.: Cray, which uses Xilinx FPGAs coupled with multiple Amd CPUs). One such example is the CELL processor on board of Sony PS3, which is powerful enough to do tridimensional processing in real time on an externally captured video stream.

In this case we have a computationally heavy, but still limited and “small” task, and want a cheap and rather immediate answer. Dedicated hardware solutions are something we use daily, e.g.: digital signal processing, sometimes without realising it, for instance when it is used within phone switching networks. DSP processing is dedicated hardware, where what you are optimising are algorithms based on repeated multiplications and additions. DSPs are fine tuned for that and may run in circles around more general and less specialised hardware such as modern Personal Computer microprocessors.

Massively huge problem, i.e. cracking RSA, Seti etc, the task at hand is so large that you cannot hope for an immediate answer. Therefore it makes sense to split the computation, which, if you are lucky will take from hours to years on a network of processing nodes. Here nothing will beat the cost of free computational power among a geografic network.

This approach makes even more sense if the network comprises volunteer nodes, which provide computational power for free, or which would have been otherwise idle (screensavers). In this latter case, the issue is not getting the intended result in the fastest way, which would be impossible with dedicated hardware as well, but rather spending as little as possible in order to obtain it. The cost of this technological approach is not really zero, but somehow you managed someone else to provide for it, gratis. You tipically design an application such as a screensaver which slowly, but on an immense scale, checks home for work, computes it, and posts a chunk of work done back home.

If cost is not an issue, nothing will stop you from using both approaches at the same time: flexibly reconfigurable hardware (ad hoc hardware, optimised for the algorithm at hand), repeated modularly on multiple systems connected on a fast network. It is not going to be cheap, but is going to resemble a lot a current supercomputer architecture.

Modern Crays are built this way. And they are based on FPGAs in order to implement special algorithms, with optimised parallel hardware, and they are reconfigurable. Why isn’t this approach adopted more often? The issue is that programming FPGAs with hardware description languages HDLs is a lot harder than programming in traditional programming languages, which are inherently serial. There are attempts to make this burden lighter, via graphical frameworks such as VIVA, or converting traditional languages in order to make them usable on these devices (some Java attempts and the more common System C).

However these tools price tags are Electronic CAD systems’ not personal computer compilers: the companys selling them need to recover millions of dollars of investiments on the few customers they have. So they won’t be adopted.

With more traditional software, you can have open source, but with FPGAs you can’t as the inner workings of their devices are something on which the two leading companies making them, that is Altera and Xilinx, keep very mum. This secrecy, in the end, damages this industry, and limits the adoption of these extremely powerful tools, which have the potential for reshaping the computing industry.

 FwLab Microcontrollers Cypress PSOC, Microchip PIC, Firmware development, Embedded Systems 

The Microcontroller, a Mutable Definition February 24, 2008

Posted by Michele Fadda in editorial, FPGA cores, microcontrollers, technology.
Tags: , , , , , , , ,
add a comment

A microcontroller is a LSI (large scale integrated) circuit containing all or most of the needed peripherals and memory, plus a Central Processing Unit, in an integrated package.

Well, this at least was, more or less the definition when it all started, around the 80-s. Nowadays that definition needs to be revised under at least two aspects: a) some modern microcontroller peripherals now are not digital b) there exist programmable logic powerful enough to implement entire subsystems, including the “microcontroller” part in a programmable array of logic. The latter are now powerful enough to offer reliably a 32 bit unit capable of running some sort of cut down Linux distribution, very slowly (50 MHz or little more are a realistic target for cheap FPGAs).

Microcontrollers containing analog circuitry are often termed “mixed signal”. They are indeed processing units, but they can do part of the work in the analog domain, e.g.: including analog filters, converters. Most of the so called “mixed signals” are just ordinary microcontrollers with an analog converter or little else. Some are quite extraordinary pieces of silicon. Among these I would place the Cypress PSOC, which is actually an analog/digital matrix plus an ordinary (and not too porful, for the time being) 8 bit microcontroller, all packaged in one chip.

The second category is the one which promises more flexibility and is potentially the most rewarding in the future.

Computer architectures are all based on variations of a common idea: the Neumann Machine, some with very slight modifications duplicating memory and peripheral communications path, the so called “Harvard architecture” (to which belong most microcontrollers including the venerable 8051). If you want to speed up things, you can introduce cache memories and pipelines, or you can try to have multiple cores, adding parallelism.

However, their main weak point, from a computational point of view is the fact that processing remains inherently sequential: the fetch and execute paradigm.

Both FPGA based cores and Mixed Analog have the potential to relieve the processing unit from some tasks, which can be ”hard-wired” (e.g.: analog filtering done in analog has a ZERO computational cost on the processing unit). FPGA cores, could, at least in theory implement entire algorithms in hardware (whether this is an “easily achieved target” is a totally different question).

As everything in a technology/engineering related field, nothing of this is optimal and easy, unless you believe 100% of the propaganda marketing communication which silicon vendors use to advertise their products. E.g. FPGA vendors try to quote as “dsp processing power” of their FPGAs the sheer multiplication result of clock frequency by the number of hardware multipliers on a chip. This leads to expectation which are exactly as reliable as the “digital gates” count they used to provide (which doesn’t make too much sense since they all use LUTs (look up tables) rather than “gates”).

Anyway, for all their limitations, these technologies are the only way to achieve the following results:

  • designing entire systems, rather rapidly, with limited resources, at an affordable cost
  • designing something which can be (potentially) reconfigure its own hardware on its own
  • trying to break Amdhal’s law
  • building your own supercomputer which runs at normal environment temperature and is small enough to fit on a desktop (which is precisely how they are using this tecnology in places like Nasa and Cray)

Why aren’t these approaches used more? Only one word: ignorance, fear, uncertainty. They are imperfect technologies, but they have a lot to offer. Start to learn today or risk be left behind. They are an essential part in the logical evolution of things like MIT’s FAB concept.

There is also another fundamental aspect: this technology is FUN, is an exciting new way of making things which you could not possibly think to do at home just a few years ago. Now this is not the future, this is here and now. 

How this tecnology is going to affect you if you are a common user and not a hardware designer? Well, expect to see electronic devices doing more with less, expect to see more creativity among designers, expect to see thing you did not expect to consider possible, as usual :-)

FwLab Professional Consulting on Embedded Systems

Follow

Get every new post delivered to your Inbox.