Hip Barcodes

PA 5 — Due: Fri Nov 3 11pm CT

Recall the academic integrity policy: turn in your own work and cite all sources.

This week we are going to make our Code 128 barcodes more hip. First, we will support switching between code sets to optimize barcode lengths. Second, we will generate and interpret barcodes as images, rather than bitstrings, using the Haskell Image Processing (HIP) Library. Lastly, there is an optional challenge idea to scan barcode images designed with some extra-hip flair.

% cabal run hip-barcodes -- encode images/barcode.png 200 5 "Hip, hip, hooray\!"
...
Wrote to:
images/barcode.png

% cabal run hip-barcodes -- decode images/barcode.png
Decoding:
Hip, hip, hooray!

Hip, but uncool…

❗ ❗ Note: HIP currently does not work with the latest version of Haskell. So, we will use a handy tool, called GHCup, that allows installing and running older versions of Haskell (see instructions below). ❗TRY IT OUT ASAP❗

Starter Code

The starter code contains several files:

• code128.csv: Same as before. U Can’t Touch This.

• Code128.hs: Copy over your previous solution, take a look at your work with fresh eyes, and refactor and polish if you wish. But don’t add any required new functionality here…

• HipBarcodes.hs: This is where the required work for this assignment will be done:

  1. Decoding
  2. Optimal Encoding (modest challenge; extra credit)
  3. Making Barcodes
  4. Scanning Barcodes
  5. Scanning Designed Barcodes (big challenge! maybe a project?)

• Tester.hs: This runs some tests on decode, encode, and scanBarcode.

• code128.cabal: This sets up two executables:

  • cabal run hip-barcodes
  • cabal run tests

  You may tweak the .cabal file with additional packages and language extensions, if needed.

  Note: Try these out and debug any cabal issues sooner rather than later.

Switching Between Code Sets

Last time, we supported barcodes encoded entirely with code set B or entirely with code set C. Now let’s support switching between code sets B and C, via the values “[Code B]” and “[Code C]”. As we will soon discuss, mixing and matching code sets allows shorter barcodes in some cases. (We are still ignoring code set A in this assignment, so “[Shift]” values will remain unsupported symbols.)

encode :: TheCodes -> String -> Either Error BC
decode :: TheCodes -> BC -> Either Error String

1. Decoding

Decoding is the easier part, so let’s start with that.

The decode function should be a relatively simple combination of decodeB and decodeC from before, plus new support for switching between code sets B and C. Consider defining a helper function for decoding that uses an argument — of type Boolean or some other two-valued type, such as data CodeSet = B | C — to track which code set is currently active.

case SOME_RESULT of
  Left err -> Left err
  Right x  -> Right $ SOME_FUNCTION x

SOME_FUNCTION <$> SOME_RESULT

2. Optimal Encoding (Extra Credit)

Optimizing barcode length during encoding is the harder part. This is optional and worth a small amount of extra credit.

Consecutive digits require one symbol using code set C instead of two symbols using B. But each switch costs a symbol.

When is it profitable to use code set C? The Wikipedia article provides a nice summary. (Below, “N+” means mean “N or more” as opposed to some kind of Haskell section!)

• When the entire string consists of digits, and the string length is either 2 or 4+ (but not 3)

  • If this number is odd, it doesn’t matter whether the first or last of these digits is encoded by C

  • However, in this assignment, we will always choose to use code set B for the first of these digits and then code set C for the rest

  • Examples:

    > run encode ""
    Right (104,[],1,106)        -- Right (105,[],2,106) is also fine
    > run encode "1"
    Right (104,[17],18,106)
    > run encode "12"
    Right (105,[12],14,106)
    > run encode "123"
    Right (104,[17,18,19],8,106)
    > run encode "1234"
    Right (105,[12,34],82,106)
    > run encode "12345"
    Right (104,[17,99,23,45],53,106)

• When 4+ consecutive digits appear at the beginning of the string

  • If this number is odd, it’s best to use code set C for all except the last of these digits

  • Examples:

    > run encodeB "1234x"
    Right (104,[17,18,19,20,88],13,106)
    > run encode "1234x"
    Right (105,[12,34,100,88],13,106)
    > run encodeB "12345x"
    Right (104,[17,18,19,20,21,88],0,106)
    > run encode "12345x"
    Right (105,[12,34,100,21,88],82,106)

• When 4+ consecutive digits appear at the end of the string

  • If this number is odd, it’s best to use code set C for all except the first of these digits

  • Examples:

    > run encodeB "x1234"
    Right (104,[88,17,18,19,20],44,106)
    > run encode "x1234"
    Right (104,[88,99,12,34],47,106)
    > run encodeB "x12345"
    Right (104,[88,17,18,19,20,21],67,106)
    > run encode "x12345"
    Right (104,[88,17,99,23,45],16,106)

• When 6+ consecutive digits appear in the middle of the string (surrounded by symbols encoded using code set B)

  • If this number is odd, it doesn’t matter whether the first or last of these digits is encoded by C

  • However, in this assignment, we will always choose to use code set B for the first of these digits and then code set C for the rest

  • Examples:

    > run encodeB "098x1234567y23"
    Right (104,[16,25,24,88,17,18,19,20,21,22,23,89,18,19],14,106)
    > run encode "098x1234567y23"
    Right (104,[16,25,24,88,17,99,23,45,67,100,89,18,19],101,106)
    > run encodeB "x123456y123456z"
    Right (104,[88,17,18,19,20,21,22,89,17,18,19,20,21,22,90],41,106)
    > run encode "x123456y123456z"
    Right (104,[88,99,12,34,56,100,89,99,12,34,56,100,90],8,106)

Hints

Turn the outline above into code. (No need for dynamic programming as suggested in the Wikipedia article, just fiddly list munging.) The first two cases — entire string and beginning of string — should be straightforward, if a bit tedious. The latter two cases — middle and end of string — are trickier.

Define simple helpers processB and processC for processing a (sub)string entirely with code set B or C, respectively.

Define a (much longer) helper which, assuming that code set B is active, takes an input string with a non-empty prefix of non-digit characters and (i) encodes that prefix with code set B and (ii) decides what to do with the rest of the string — with the help of all the helpers.

Check out these standard Prelude functions:

span :: (a -> Bool) -> [a] -> ([a], [a])

splitAt :: Int -> [a], ([a], [a])

even :: Integral a => a -> Bool

odd :: Integral a => a -> Bool

> span isDigit "01234abc56789de"
("01234","abc56789de")

> splitAt 1 [1..10]
([1],[2,3,4,5,6,7,8,9,10])

HIP Library

We will use the Haskell Image Processing (HIP) Library to manipulate barcode images.

The build-depends entry of our .cabal file includes hip, a package containing modules Graphics.Image, Graphics.Image.ColorSpace, Graphics.Image.Interface, and more.

% cabal build
...
[__3] skipping: base-4.18.0.0, base-4.17.1.0, base-4.17.0.0 (has the same
characteristics that caused the previous version to fail: excluded by
constraint '>=4.8 && <4.17' from 'repa')
...
[__3] fail (backjumping, conflict set: base, hip-barcodes, repa)
...

GHCup

There is a nice tool called GHCup to manage the installation of updates to GHC and associated tools.

See what versions of GHC and related tools are installed on your machine:

% ghcup list

To get HIP to work, install the following older version:

% ghcup install ghc 9.2.8

To set which version of GHC is active:

% ghcup set ghc 9.2.8
[ Info  ] GHC 9.2.8 successfully set as default version

Check that you are now running the older version:

%  ghci
GHCi, version 9.2.8: https://www.haskell.org/ghc/  :? for help
>

When you’re done working on this assignment, you can reset things to the most recent version. You can do that by running set without a version number:

% ghcup set ghc
[ Info  ] GHC 9.4.7 successfully set as default version

% ghcup tui

Cabal

Try this right now to make sure your development environment works.

% cabal build

In addition to compiling, also check that you can access hip via GHCi for interactively exploring the library and testing your program. (Notice the handy cabal repl command, which will launch ghc and load the packages listed in the .cabal file.)

% cabal repl hip-barcodes
> import Graphics.Image

% ghci
> :set -package hip
> import Graphics.Image

% cabal install --lib hip
% ghci
> import Graphics.Image

Overview

Part of the goal in this assignment is to practice working with a large library… even if we don’t grok all the types and type classes and type families (a Haskell feature we are not discussing in this course) and multi-parameter type classes (another such feature).

You will likely need only a handful of functions provided by the library. As a first example, the following loads an image and gets a pixel at a given position:

> :set -package hip
> import Graphics.Image
> img <- readImageRGB VU "images/barcode-1.png"
> let pixel = index img (0, 0)
> pixel
<RGB:(0.0|0.0|0.0)>
> let PixelRGB r g b = pixel in (r, g, b)
(0.0,0.0,0.0)
> toPixelY pixel
<Luma:(0.0)>
> let PixelY y = toPixelY pixel in y
0.0

This example demonstrates:

• readImageRGB, where VU is one of the internal Array representations of the data
• index
• PixelRGB and PixelY, where PixelY values are defined by a single grayscale number (a “Luma”)
• toPixelY converts to Luma, via a class called ToY

Now consider a second example, that creates an image:

> cabal repl hip-barcodes
> import Graphics.Image
> let grayscale :: Image VU Y Double = makeImageR VU (200, 200) (\(i, j) -> PixelY (fromIntegral i / 200))
> writeImage "images/grayscale.png" grayscale

This example demonstrates:

• makeImageR
• writeImage

Not demonstrated above, but a few more possibly helpful functions, among others:

• dims, rows, cols

3. Making Barcodes

Now that you’re hip to HIP, it’s time to get barcoding!

First, a function for generating barcode images:

makeBarcode :: FilePath -> Int -> Int -> BCString -> IO ()
makeBarcode filePath imageHeight moduleWidth (BCString symbols) =
  ...

The imageHeight is specified in pixels, and moduleWidth argument is the number of pixels for each module. The image should not have quiet zones on the left or right, nor any padding on top or bottom.

4. Scanning Barcodes

Next, implement a barcode “scanner.” Given a “perfect” barcode image generated from makeBarcode (no rotation, no graininess, no defects whatsover), decode it:

scanBarcode :: FilePath -> IO BCString
scanBarcode filePath =
  ...

Consider implementing the following helper functions. (No need to worry about MArray — just note VU is a member of this class.)

imageToBCString :: (MArray arr cs e, ToY cs e) => Image arr cs e -> BCString

isBlack :: (ToY cs e) => Pixel cs e -> Bool

It is important to notice that scanBarcode does not know either the imageHeight or the moduleWidth that was used to create the image. Do not assume they are 200 and 5 as in the sample at the top of the page. Determining the height is not a big deal. Determining module width requires a bit of finagling. Consider implementing and using the following two helpers:

getModuleWidth :: [Bool] -> Int

takeEvery :: Int -> [a] -> [a]

Tests

The images/ directory in the starter code provides a handful of barcodes to test:

% cabal run hip-barcodes -- decode images/barcode-0.png | grep -A1 Decoding
Decoding:
Hip, hip, hooray!

% cabal run hip-barcodes -- decode images/barcode-1.png | grep -A1 Decoding
Decoding:
Haskell!

% cabal run hip-barcodes -- decode images/barcode-2.png | grep -A1 Decoding
Decoding:
CMSC 22300? HOT Programming in Haskell!

% cabal run hip-barcodes -- decode images/barcode-3.png | grep -A1 Decoding
Decoding:
3141592653

% cabal run hip-barcodes -- decode images/barcode-4.png | grep -A1 Decoding
Decoding:
098x1234567y23

These tests are also included in Tester.hs:

% cabal run tests

5. Scanning Designed Barcodes (Optional)

Wikipedia showcases some “designed barcodes”:

If you’re up for a lot more work and fun (maybe the seed of a project idea?), define another function, called scanDesignedBarcode, that recognizes barcodes with some extra flair. The challenge is to recognize as many of the examples above (and others like them) as possible. Unlike the simple, ideal barcode images supported by scanBarcode, this version will need to do much more — to identify which pixels comprise the barcode data, to tolerate noise, and so on.

While you’re at it, you might also design your own designed barcodes, either programmatically with Haskell/HIP, or with a graphic design tool, or some combination of both. If you do, tell us about what you made and share them with the world to enjoy.

Grading

Here is an outline of the grading rubric (10 points total):

• 3.0 decode
• 0.0 encode (extra credit: +1.0)
• 3.0 makeBarcode
• 3.0 scanBarcode
• 1.0 Clean (Haskell) code (based on the style guidelines)

Sanity Check

Once you are finished, check that you added, committed, and pushed everything to your repository before the deadline (or within an eligible late period):

https://github.com/UChicago-PL/cs223-fa23-pa-5-hip-barcodes-USERNAME

Misc

• Functional Image Synthesis, Conal Elliott (2001)

• Workshop on Functional Art, Music, Modeling and Design