Background

Densely packed decimal (DPD) is a way to efficiently store decimal digits in binary. It stores three decimal digits (000 to 999) in 10 bits, which is much more efficient than naive BCD (which stores one digit in 4 bits).

Notations

• The lowercase alphabets a to i are the bits that are copied to the decimal representation.


• 
  0 and 1 are the exact bits in the input or output bit patterns.


• 
  x bits are ignored in the conversion.

Conversion table

The following is the conversion table from 10 bits of DPD to three decimal digits. Each decimal digit is represented as 4-bit binary (BCD). Both sides are written left to right from the most significant digit to the least.

Bits                 =>  Decimal         (Digit range)

a b c d e f 0 g h i  =>  0abc 0def 0ghi  (0-7) (0-7) (0-7)

a b c d e f 1 0 0 i  =>  0abc 0def 100i  (0–7) (0–7) (8–9)

a b c g h f 1 0 1 i  =>  0abc 100f 0ghi  (0–7) (8–9) (0–7)

g h c d e f 1 1 0 i  =>  100c 0def 0ghi  (8–9) (0–7) (0–7)

g h c 0 0 f 1 1 1 i  =>  100c 100f 0ghi  (8–9) (8–9) (0–7)

d e c 0 1 f 1 1 1 i  =>  100c 0def 100i  (8–9) (0–7) (8–9)

a b c 1 0 f 1 1 1 i  =>  0abc 100f 100i  (0–7) (8–9) (8–9)

x x c 1 1 f 1 1 1 i  =>  100c 100f 100i  (8–9) (8–9) (8–9)

Task

Convert 10 bits of DPD to 3 digits of decimal.

Test cases

DPD           Decimal

0000000101    005

0001100011    063

0001111001    079

0000011010    090

0001011110    098

1010111010    592

0011001101    941

1100111111    879

1110001110    986

0011111111    999

1111111111    999  * Output is same regardless of the `x` bits

Input

The default input format is a list of 10 bits. The bits should follow the exact order above, or the reverse of it. You may choose to use an equivalent string or integer representation instead. Unlike my other challenges, reordering or using nested structures is not allowed.

For the input [1, 1, 0, 0, 0, 1, 0, 1, 0, 0], the following formats are allowed:

• List of bits: [1, 1, 0, 0, 0, 1, 0, 1, 0, 0]
  


• String: "1100010100"
  


• Binary integer: 788 or 0b1100010100
  


• Decimal integer: 1100010100
  


• Reversed: [0, 0, 1, 0, 1, 0, 0, 0, 1, 1] and reversed in any other formats above

The following formats are NOT allowed:

• Arbitrary reordering of bits: [0, 0, 0, 0, 0, 1, 1, 1, 0, 1]
  


• Nested structures: [[1, 1, 0], [0, 0, 1], [0, 1, 0, 0]] or [0b110, 0b001, 0b0100]
  

Output

The default output format is a list of 3 decimal digits. Each digit should be represented as 0 to 9, either an integer or a character. As in input, you can choose string or integer representation. If you choose integer representation, leading zeroes can be omitted.

Scoring & winning criterion

Standard code-golf rules apply. The shortest program or function in bytes for each language wins.

JavaScript (ES6), 118 117 bytes

Takes input as an integer. Returns an array of three decimal digits.

n=>[(x=n>>4&7,y=n>>7,p=n/2&7)>5&&p<7|x/2^2?8|y&1:y,(p<7?p-5?x:8:x/2^1?8:y&6)|x&1,(p<5?p*2:p<6?x&6:p<7|x<2?y&6:8)|n&1]

Try it online!

How?

Instead of trying to apply the 'official' algorithm, this code is based on some kind of reverse-engineering of the patterns that can be found in the expected results.

Given the input integer $n$, we compute:

$$begin{align}&x=leftlfloorfrac{n}{16}rightrfloor bmod 8\
&y=leftlfloorfrac{n}{128}rightrfloor\
&p=leftlfloorfrac{n}{2}rightrfloor bmod 8end{align}
$$

Example: first digit (hundreds)

x     | 0                | 1                | 2                | 3               

n & 1 | 0101010101010101 | 0101010101010101 | 0101010101010101 | 0101010101010101

p     | 0011223344556677 | 0011223344556677 | 0011223344556677 | 0011223344556677

------+------------------+------------------+------------------+-----------------

y = 0 | 0000000000008888 | 0000000000008888 | 0000000000008888 | 0000000000008888

y = 1 | 1111111111119999 | 1111111111119999 | 1111111111119999 | 1111111111119999

y = 2 | 2222222222228888 | 2222222222228888 | 2222222222228888 | 2222222222228888

y = 3 | 3333333333339999 | 3333333333339999 | 3333333333339999 | 3333333333339999

y = 4 | 4444444444448888 | 4444444444448888 | 4444444444448888 | 4444444444448888

y = 5 | 5555555555559999 | 5555555555559999 | 5555555555559999 | 5555555555559999

y = 6 | 6666666666668888 | 6666666666668888 | 6666666666668888 | 6666666666668888

y = 7 | 7777777777779999 | 7777777777779999 | 7777777777779999 | 7777777777779999



x     | 4                | 5                | 6                | 7               

n & 1 | 0101010101010101 | 0101010101010101 | 0101010101010101 | 0101010101010101

p     | 0011223344556677 | 0011223344556677 | 0011223344556677 | 0011223344556677

------+------------------+------------------+------------------+-----------------

y = 0 | 0000000000008800 | 0000000000008800 | 0000000000008888 | 0000000000008888

y = 1 | 1111111111119911 | 1111111111119911 | 1111111111119999 | 1111111111119999

y = 2 | 2222222222228822 | 2222222222228822 | 2222222222228888 | 2222222222228888

y = 3 | 3333333333339933 | 3333333333339933 | 3333333333339999 | 3333333333339999

y = 4 | 4444444444448844 | 4444444444448844 | 4444444444448888 | 4444444444448888

y = 5 | 5555555555559955 | 5555555555559955 | 5555555555559999 | 5555555555559999

y = 6 | 6666666666668866 | 6666666666668866 | 6666666666668888 | 6666666666668888

y = 7 | 7777777777779977 | 7777777777779977 | 7777777777779999 | 7777777777779999

Algorithm:

• If $p<6$, we have $d=y$
  


• If $p=6$, we have $d=8+(ybmod2)$
  


• If $p=7text{ AND }(x<4text{ OR }x>5)$, we have $d=8+(ybmod2)$
  


• If $p=7text{ AND }(x=4text{ OR }x=5)$, we have $d=y$
  

As JS code:

p > 5 && p < 7 | x / 2 ^ 2 ? 8 | y & 1 : y

JavaScript (Node.js), 126 119 117 112 bytes

(a,b,c,d,e,f,g,h,i,j)=>[(g&h&i+(b+=a*4+b,e+=d*4+e)!=5?8:b)+c,(g&i?h+e-3?8:b:e)+f,(g?h-i|h&!e?h?b:e:8:h*4+i*2)+j]

Try it online!

-5 bytes thanks @tsh (and 2 by myself) So l can make more effort than I expected.

-2 more bytes using @tsh's technique!

-5 bytes thanks @Arnauld

Input as a list of 10 bits (as 10 arguments), output as a list of 3 digits.

C (gcc), 138 129 bytes

f(w){int t=w/2&55,s=t%8,v=w/16,u=v/8;w=((s<6|t==39?u:8|u%2)*10+v%2+(s&5^5?v&6:t-23?8:u&6))*10+w%2+(s<5?s*2:s<6?v&6:s%t<7?u&6:8);}

Try it online!

First extracts some bits into variables s and t, so that the eight rows of the conversion table can be identified by:

1.  s < 4              u v w¹

2.  s = 4              u v 8¹

3.  s = 5              u 8 v

4.  s = 6              8 v u

5.  s = 7, t =  7      8 8 u

6.  s = 7, t = 23      8 u 8

7.  s = 7, t = 39      u 8 8

8.  s = 7, t = 55      8 8 8



¹ Can be computed with s*2

Then sets up u and v with divisions (right shifts), so that u, v and the input w contain the lower three BCD bits in positions 0-2. The rest is bit shuffling depending on s and t. Two notable tricks are:

s&5^5  // Rows 1, 2 and 4.

s%t<7  // Rows 1-5.

Ruby, 153 ... 119 117 bytes

->n{n+=n&896;a,b,c=n&1536,n&96,n&14;"%x"%n+=c<9?0:2036+[b/16-b-1918,r=a>>8,[r+126,a/16-26,a-1978,38][b/32]-a][c/2-5]}

Try it online!

How it works:

->n{n+=n&896;

This is the starting point: convert to BCD by shifting 3 bits to the left, which works for most of the patterns.

a,b,c=n&1536,n&96,n&14;

Get the middle bits of each nibble (and one extra bit of the third nibble, but mask the least significant bit).

"%x"%n+=c<9?0

If the third digit is less than 10 (less than 9 because we never cared for the LSB anyway), we're set: this is plain BCD, we can output the hex without changing anything

:2036+[b/16-b-1918,r=a>>8,[r+126,a/16-26,a-1978,38][b/32]-a][c/2-5]}

Otherwise do some black magic by shifting bits around and adding magic numbers until we get the result we want.

Python 3, 229 194 184 170 160 158 126 122 121 bytes

lambda a,b,c,d,e,f,g,h,i,j:[[2*h+i,2*d+e,2*a+b,4][b"ie/]OBWs"[-g&(2*h+i-3or 2*d+e)+4]%x&3]*2+[j,f,c][x-7]for x in[9,8,7]]

Try it online!

-4 bytes by xnor

Formatted:

h = lambda a,b,c,d,e,f,g,h,i,j:[

    [2*h+i,2*d+e,2*a+b,4][               List to take high bits from

        b"ie/]OBWs"[                     8 char string; where to get high bits for

                                           each of 8 possible indicator values

            -g&(2*h+i-3or 2*d+e)+4       Compute indicator

            ]%x&3]*2+                    High bits of each digit

        [j,f,c][x-7]                     Low bit of each digit

    for x in[9,8,7]]

Explanation

Because I originally wanted to implement this in Jelly, I take a different approach from most answers here, which is simple and perhaps more suited to a golfing language. Let the input bit list be [a0,a1,...,a9]. Then we can derive three variables from the indicator

• The low bits [a2,a5,a9]: These will always be the low bits of [d0,d1,d2] respectively.


• The high bits [a0a1,a3a4,a7a8,4]: The high bits of each digit will either be one of these.


• The indicator bits, [a3,a4,a5,a7,a8], determining how to get the high bits of each digit. We compute the indicator (between 0 and 7) as follows:
  
  
  
  
  • If a5 == 0, the indicator is 0
  
  
  • If a3 nand a4, the indicator is a3a4 + 1
  
  
  • Otherwise the indicator is a7a8 + 4.
  
  
  
  

Then the high bit of digit d can be elegantly computed as [high_bits][arr[indicator][d]] by the table below, which can be compressed into a string.

arr = [

    [0,1,2],

    [3,1,2],

    [1,3,2],

    [2,1,3],

    [2,3,3],

    [3,2,3],

    [3,3,2],

    [3,3,3]

]

Alternate solution taking input as a list (158 bytes, can be golfed to ~130):

lambda a:[a[i]+h*2for h,i in zip([([2*a[j-1]+a[j]for j in[8,4,1]]+[4])[ord("$'-6>;/?"[a[6]and(2*a[7]+a[8]-3or 2*a[3]+a[4])+4])>>x&3]for x in[4,2,0]],[2,5,9])]