taler-android

Android apps for GNU Taler (wallet, PoS, cashier)
Log | Files | Refs | README | LICENSE

qr-camera-ignores-the-plane-strides.diff (21941B)


      1 diff --git a/taler-kotlin-android/src/main/java/net/taler/lib/android/qr/QrCameraAnalyzer.kt b/taler-kotlin-android/src/main/java/net/taler/lib/android/qr/QrCameraAnalyzer.kt
      2 index de9d94ca..5fb26e3f 100644
      3 --- a/taler-kotlin-android/src/main/java/net/taler/lib/android/qr/QrCameraAnalyzer.kt
      4 +++ b/taler-kotlin-android/src/main/java/net/taler/lib/android/qr/QrCameraAnalyzer.kt
      5 @@ -19,6 +19,7 @@ package net.taler.lib.android.qr
      6  import android.content.Context
      7  import android.graphics.Bitmap
      8  import android.media.Image
      9 +import android.util.Log
     10  import androidx.camera.core.Camera
     11  import androidx.camera.core.CameraSelector
     12  import androidx.camera.core.ExperimentalGetImage
     13 @@ -38,7 +39,62 @@ import com.google.zxing.RGBLuminanceSource
     14  import com.google.zxing.BarcodeFormat
     15  import com.google.zxing.common.HybridBinarizer
     16  import com.google.zxing.PlanarYUVLuminanceSource
     17 +import java.nio.ByteBuffer
     18 +import java.util.concurrent.ExecutorService
     19  import java.util.concurrent.Executor
     20 +import java.util.concurrent.Executors
     21 +
     22 +/**
     23 + * The luminance plane of a YUV_420_888 frame, with its padding removed.
     24 + *
     25 + * A camera plane is not a tightly packed image: `rowStride` may exceed the
     26 + * width (the hardware pads each row) and `pixelStride` may exceed one (the
     27 + * samples are interleaved).  Copying the buffer in one `get()` is only correct
     28 + * when neither is true, and when a row is padded every row after the first
     29 + * lands shifted, so the image skews and nothing decodes.  Whether a given
     30 + * camera pads depends on the device *and* the platform version, which is how
     31 + * scanning can work on one Android release and fail on another.
     32 + *
     33 + * zxing's [PlanarYUVLuminanceSource] reads only this plane, so the chroma
     34 + * layout does not matter -- this is the whole of what the decoder needs.
     35 + */
     36 +internal fun extractLuma(
     37 +    buffer: ByteBuffer,
     38 +    rowStride: Int,
     39 +    pixelStride: Int,
     40 +    width: Int,
     41 +    height: Int,
     42 +): ByteArray {
     43 +    val luma = ByteArray(width * height)
     44 +    if (rowStride == width && pixelStride == 1) {
     45 +        // The common case: already tightly packed.
     46 +        buffer.position(0)
     47 +        buffer.get(luma, 0, minOf(luma.size, buffer.remaining()))
     48 +        return luma
     49 +    }
     50 +    val row = ByteArray(rowStride)
     51 +    var out = 0
     52 +    for (y in 0 until height) {
     53 +        val start = y * rowStride
     54 +        if (start >= buffer.limit()) break
     55 +        buffer.position(start)
     56 +        // The last row is often short: the plane need not include its padding.
     57 +        val len = minOf(rowStride, buffer.remaining())
     58 +        buffer.get(row, 0, len)
     59 +        if (pixelStride == 1) {
     60 +            System.arraycopy(row, 0, luma, out, minOf(width, len))
     61 +        } else {
     62 +            var x = 0
     63 +            while (x < width && x * pixelStride < len) {
     64 +                luma[out + x] = row[x * pixelStride]
     65 +                x++
     66 +            }
     67 +        }
     68 +        out += width
     69 +    }
     70 +    return luma
     71 +}
     72 +
     73  
     74  @androidx.annotation.OptIn(ExperimentalGetImage::class)
     75  class QrCameraAnalyzer(
     76 @@ -49,6 +105,14 @@ class QrCameraAnalyzer(
     77      private val onCameraReady: ((initialLinearZoom: Float) -> Unit)? = null,
     78  ) {
     79      private val mainExecutor: Executor = ContextCompat.getMainExecutor(context)
     80 +
     81 +    /**
     82 +     * Frames are analysed here, not on the main thread: a frame costs a
     83 +     * copy of the luminance plane plus a zxing decode, which is work the UI
     84 +     * thread should not be doing thirty times a second.  One thread, so the
     85 +     * reader below needs no locking.
     86 +     */
     87 +    private val analysisExecutor: ExecutorService = Executors.newSingleThreadExecutor()
     88      private var camera: Camera? = null
     89  
     90      private val qrReader = MultiFormatReader().apply {
     91 @@ -72,34 +136,21 @@ class QrCameraAnalyzer(
     92              val analysis = ImageAnalysis.Builder()
     93                  .setBackpressureStrategy(ImageAnalysis.STRATEGY_KEEP_ONLY_LATEST)
     94                  .build().also { useCase ->
     95 -                    useCase.setAnalyzer(mainExecutor) { proxy ->
     96 -                        val mediaImage = proxy.image
     97 -                        if (mediaImage != null) {
     98 -                            val nv21 = yuv420888ToNv21(mediaImage)
     99 -                            val width = mediaImage.width
    100 -                            val height = mediaImage.height
    101 -                            val rotation = proxy.imageInfo.rotationDegrees
    102 -
    103 -                            val (rotatedNv21, rotatedWidth, rotatedHeight) = when (rotation) {
    104 -                                90 -> rotateNV21(nv21, width, height, 90)
    105 -                                180 -> rotateNV21(nv21, width, height, 180)
    106 -                                270 -> rotateNV21(nv21, width, height, 270)
    107 -                                else -> Triple(nv21, width, height)
    108 +                    useCase.setAnalyzer(analysisExecutor) { proxy ->
    109 +                        // Whatever happens to this frame, the proxy has to be
    110 +                        // closed: with STRATEGY_KEEP_ONLY_LATEST an unclosed
    111 +                        // one stops frame delivery for good, so a single
    112 +                        // unexpected frame would end scanning for the rest of
    113 +                        // the session while the viewfinder kept running.
    114 +                        try {
    115 +                            proxy.image?.let { image ->
    116 +                                decodeQr(image)?.let { text ->
    117 +                                    mainExecutor.execute { onQrDetected(text) }
    118 +                                }
    119                              }
    120 -
    121 -                            val source = PlanarYUVLuminanceSource(
    122 -                                rotatedNv21, rotatedWidth, rotatedHeight, 0, 0, rotatedWidth, rotatedHeight, false,
    123 -                            )
    124 -
    125 -                            val bitmap = BinaryBitmap(HybridBinarizer(source))
    126 -                            try {
    127 -                                val result = qrReader.decodeWithState(bitmap)
    128 -                                onQrDetected(result.text)
    129 -                            } catch (_: NotFoundException) {
    130 -                            } finally {
    131 -                                proxy.close()
    132 -                            }
    133 -                        } else {
    134 +                        } catch (e: Exception) {
    135 +                            Log.w(TAG, "could not analyse a camera frame", e)
    136 +                        } finally {
    137                              proxy.close()
    138                          }
    139                      }
    140 @@ -124,6 +175,7 @@ class QrCameraAnalyzer(
    141              camera = null
    142          } catch (_: Exception) {
    143          }
    144 +        analysisExecutor.shutdown()
    145      }
    146  
    147      fun enableTorch(enabled: Boolean) {
    148 @@ -147,84 +199,37 @@ class QrCameraAnalyzer(
    149          cam.cameraControl.startFocusAndMetering(action)
    150      }
    151  
    152 -    private fun yuv420888ToNv21(image: Image): ByteArray {
    153 -        val yPlane = image.planes[0].buffer
    154 -        val uPlane = image.planes[1].buffer
    155 -        val vPlane = image.planes[2].buffer
    156 -        val ySize = yPlane.remaining()
    157 -        val uSize = uPlane.remaining()
    158 -        val vSize = vPlane.remaining()
    159 -        val nv21 = ByteArray(ySize + uSize + vSize)
    160 -        yPlane.get(nv21, 0, ySize)
    161 -        vPlane.get(nv21, ySize, vSize)
    162 -        uPlane.get(nv21, ySize + vSize, uSize)
    163 -        return nv21
    164 -    }
    165 -
    166 -    private fun rotateNV21(data: ByteArray, width: Int, height: Int, rotation: Int): Triple<ByteArray, Int, Int> {
    167 -        if (rotation == 0) return Triple(data, width, height)
    168 -
    169 -        val ySize = width * height
    170 -        val uvSize = ySize / 2
    171 -        val rotated = ByteArray(ySize + uvSize)
    172 -
    173 -        when (rotation) {
    174 -            90 -> {
    175 -                var i = 0
    176 -                for (x in 0 until width) {
    177 -                    for (y in height - 1 downTo 0) {
    178 -                        rotated[i++] = data[y * width + x]
    179 -                    }
    180 -                }
    181 -                var uvIndex = ySize
    182 -                for (x in 0 until width step 2) {
    183 -                    for (y in height - 1 downTo 0 step 2) {
    184 -                        val uvPos = ySize + (y * width + x)
    185 -                        if (uvPos + 1 < data.size) {
    186 -                            rotated[uvIndex++] = data[uvPos]
    187 -                            rotated[uvIndex++] = data[uvPos + 1]
    188 -                        }
    189 -                    }
    190 -                }
    191 -                return Triple(rotated, height, width)
    192 -            }
    193 -            180 -> {
    194 -                var i = ySize - 1
    195 -                for (j in 0 until ySize) {
    196 -                    rotated[j] = data[i--]
    197 -                }
    198 -                i = data.size - 1
    199 -                for (j in ySize until data.size step 2) {
    200 -                    rotated[j] = data[i - 1]
    201 -                    rotated[j + 1] = data[i]
    202 -                    i -= 2
    203 -                }
    204 -                return Triple(rotated, width, height)
    205 -            }
    206 -            270 -> {
    207 -                var i = 0
    208 -                for (x in width - 1 downTo 0) {
    209 -                    for (y in 0 until height) {
    210 -                        rotated[i++] = data[y * width + x]
    211 -                    }
    212 -                }
    213 -                var uvIndex = ySize
    214 -                for (x in width - 1 downTo 0 step 2) {
    215 -                    for (y in 0 until height step 2) {
    216 -                        val uvPos = ySize + (y * width + x - 1)
    217 -                        if (uvPos + 1 < data.size) {
    218 -                            rotated[uvIndex++] = data[uvPos]
    219 -                            rotated[uvIndex++] = data[uvPos + 1]
    220 -                        }
    221 -                    }
    222 -                }
    223 -                return Triple(rotated, height, width)
    224 -            }
    225 +    /**
    226 +     * The `taler://` URI in [image], or null if there is no QR code in it.
    227 +     *
    228 +     * The frame is not rotated first.  zxing locates a QR code by its three
    229 +     * finder patterns and derives the orientation from them, so it reads a
    230 +     * code the same whichever way up the phone is held -- rotating the plane
    231 +     * by hand only cost a second pass over every pixel.
    232 +     */
    233 +    private fun decodeQr(image: Image): String? {
    234 +        val plane = image.planes[0]
    235 +        val luma = extractLuma(
    236 +            plane.buffer,
    237 +            plane.rowStride,
    238 +            plane.pixelStride,
    239 +            image.width,
    240 +            image.height,
    241 +        )
    242 +        val source = PlanarYUVLuminanceSource(
    243 +            luma, image.width, image.height, 0, 0, image.width, image.height, false,
    244 +        )
    245 +        return try {
    246 +            qrReader.decodeWithState(BinaryBitmap(HybridBinarizer(source))).text
    247 +        } catch (_: NotFoundException) {
    248 +            // Most frames hold no code at all; this is the ordinary case.
    249 +            null
    250          }
    251 -        return Triple(data, width, height)
    252      }
    253  
    254      companion object {
    255 +        private const val TAG = "QrCameraAnalyzer"
    256 +
    257          fun decodeQrFromBitmap(bitmap: Bitmap): String? {
    258              val width = bitmap.width
    259              val height = bitmap.height
    260 diff --git a/taler-kotlin-android/src/test/java/net/taler/lib/android/qr/ExtractLumaTest.kt b/taler-kotlin-android/src/test/java/net/taler/lib/android/qr/ExtractLumaTest.kt
    261 new file mode 100644
    262 index 00000000..63f84f7f
    263 --- /dev/null
    264 +++ b/taler-kotlin-android/src/test/java/net/taler/lib/android/qr/ExtractLumaTest.kt
    265 @@ -0,0 +1,104 @@
    266 +/*
    267 + * This file is part of GNU Taler
    268 + * (C) 2026 Taler Systems S.A.
    269 + *
    270 + * GNU Taler is free software; you can redistribute it and/or modify it under the
    271 + * terms of the GNU General Public License as published by the Free Software
    272 + * Foundation; either version 3, or (at your option) any later version.
    273 + *
    274 + * GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
    275 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
    276 + * A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
    277 + *
    278 + * You should have received a copy of the GNU General Public License along with
    279 + * GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
    280 + */
    281 +
    282 +package net.taler.lib.android.qr
    283 +
    284 +import org.junit.Assert.assertArrayEquals
    285 +import org.junit.Test
    286 +import java.nio.ByteBuffer
    287 +
    288 +/**
    289 + * A camera's luminance plane is not a tightly packed image, and the QR decoder
    290 + * only works if the padding is taken out.  How a plane is laid out depends on
    291 + * the device and the platform version, which is why this is worth pinning:
    292 + * reading it wrong shows up as "scanning works on one Android release and not
    293 + * on another" rather than as an obvious failure.
    294 + */
    295 +class ExtractLumaTest {
    296 +
    297 +    /** Row y, column x of a test image, as a recognisable byte. */
    298 +    private fun pixel(x: Int, y: Int) = (y * 16 + x).toByte()
    299 +
    300 +    private fun expected(width: Int, height: Int) = ByteArray(width * height) {
    301 +        pixel(it % width, it / width)
    302 +    }
    303 +
    304 +    @Test
    305 +    fun tightlyPackedPlaneIsCopiedAsIs() {
    306 +        val width = 4
    307 +        val height = 3
    308 +        val buffer = ByteBuffer.wrap(expected(width, height))
    309 +        assertArrayEquals(
    310 +            expected(width, height),
    311 +            extractLuma(buffer, rowStride = width, pixelStride = 1, width, height),
    312 +        )
    313 +    }
    314 +
    315 +    @Test
    316 +    fun paddedRowsDoNotShiftTheImage() {
    317 +        val width = 4
    318 +        val height = 3
    319 +        val rowStride = 7 // the hardware pads each row by three bytes
    320 +        val padded = ByteArray(rowStride * height) { 0x7F }
    321 +        for (y in 0 until height) {
    322 +            for (x in 0 until width) padded[y * rowStride + x] = pixel(x, y)
    323 +        }
    324 +        assertArrayEquals(
    325 +            expected(width, height),
    326 +            extractLuma(ByteBuffer.wrap(padded), rowStride, pixelStride = 1, width, height),
    327 +        )
    328 +    }
    329 +
    330 +    @Test
    331 +    fun interleavedSamplesAreTakenEveryPixelStride() {
    332 +        val width = 4
    333 +        val height = 2
    334 +        val pixelStride = 2
    335 +        val rowStride = width * pixelStride
    336 +        val interleaved = ByteArray(rowStride * height) { 0x7F }
    337 +        for (y in 0 until height) {
    338 +            for (x in 0 until width) {
    339 +                interleaved[y * rowStride + x * pixelStride] = pixel(x, y)
    340 +            }
    341 +        }
    342 +        assertArrayEquals(
    343 +            expected(width, height),
    344 +            extractLuma(ByteBuffer.wrap(interleaved), rowStride, pixelStride, width, height),
    345 +        )
    346 +    }
    347 +
    348 +    @Test
    349 +    fun aPlaneWithoutTrailingPaddingIsStillRead() {
    350 +        // Some cameras stop the plane after the last row's pixels, so the
    351 +        // buffer is rowStride * (height - 1) + width bytes, not rowStride *
    352 +        // height.  Reading past that must not throw.
    353 +        val width = 4
    354 +        val height = 3
    355 +        val rowStride = 6
    356 +        val size = rowStride * (height - 1) + width
    357 +        val plane = ByteArray(size) { 0x7F }
    358 +        for (y in 0 until height) {
    359 +            for (x in 0 until width) {
    360 +                val at = y * rowStride + x
    361 +                if (at < size) plane[at] = pixel(x, y)
    362 +            }
    363 +        }
    364 +        assertArrayEquals(
    365 +            expected(width, height),
    366 +            extractLuma(ByteBuffer.wrap(plane), rowStride, pixelStride = 1, width, height),
    367 +        )
    368 +    }
    369 +}
    370 diff --git a/taler-kotlin-android/src/test/java/net/taler/lib/android/qr/QrFrameDecodeTest.kt b/taler-kotlin-android/src/test/java/net/taler/lib/android/qr/QrFrameDecodeTest.kt
    371 new file mode 100644
    372 index 00000000..9bdc6ba8
    373 --- /dev/null
    374 +++ b/taler-kotlin-android/src/test/java/net/taler/lib/android/qr/QrFrameDecodeTest.kt
    375 @@ -0,0 +1,163 @@
    376 +/*
    377 + * This file is part of GNU Taler
    378 + * (C) 2026 Taler Systems S.A.
    379 + *
    380 + * GNU Taler is free software; you can redistribute it and/or modify it under the
    381 + * terms of the GNU General Public License as published by the Free Software
    382 + * Foundation; either version 3, or (at your option) any later version.
    383 + *
    384 + * GNU Taler is distributed in the hope that it will be useful, but WITHOUT ANY
    385 + * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
    386 + * A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
    387 + *
    388 + * You should have received a copy of the GNU General Public License along with
    389 + * GNU Taler; see the file COPYING.  If not, see <http://www.gnu.org/licenses/>
    390 + */
    391 +
    392 +package net.taler.lib.android.qr
    393 +
    394 +import com.google.zxing.BarcodeFormat
    395 +import com.google.zxing.BinaryBitmap
    396 +import com.google.zxing.DecodeHintType
    397 +import com.google.zxing.EncodeHintType
    398 +import com.google.zxing.MultiFormatReader
    399 +import com.google.zxing.NotFoundException
    400 +import com.google.zxing.PlanarYUVLuminanceSource
    401 +import com.google.zxing.common.HybridBinarizer
    402 +import com.google.zxing.qrcode.QRCodeWriter
    403 +import org.junit.Assert.assertEquals
    404 +import org.junit.Assert.assertNull
    405 +import org.junit.Test
    406 +import java.nio.ByteBuffer
    407 +
    408 +/**
    409 + * The camera half of QR scanning, end to end, without a camera.
    410 + *
    411 + * A camera frame is only a luminance plane plus the two numbers that say how
    412 + * it is laid out, so a frame can be built here and put through the same
    413 + * decoder the analyzer uses.  That covers the part of scanning that no
    414 + * emulator can test -- the virtual camera cannot be pointed at a code -- and
    415 + * it covers it on every device layout at once rather than on whichever one the
    416 + * test phone happens to use.
    417 + */
    418 +class QrFrameDecodeTest {
    419 +
    420 +    private val payload = "taler://pay/backend.demo.taler.net/2026.123-02B5CYNPRHXRC/"
    421 +
    422 +    private val width = 640
    423 +    private val height = 480
    424 +    private val codeSize = 400
    425 +
    426 +    /**
    427 +     * The luminance plane of a frame with the code centred on white, laid out
    428 +     * with [rowStride] bytes per row and [pixelStride] bytes per sample.
    429 +     * [rowStride] counts bytes, so an interleaved plane needs at least
    430 +     * `width * pixelStride` of them.
    431 +     */
    432 +    private fun frame(rowStride: Int = width, pixelStride: Int = 1): ByteArray {
    433 +        val matrix = QRCodeWriter().encode(
    434 +            payload, BarcodeFormat.QR_CODE, codeSize, codeSize,
    435 +            mapOf(EncodeHintType.MARGIN to 1),
    436 +        )
    437 +        val plane = ByteArray(rowStride * height) { -1 } // white
    438 +        val left = (width - codeSize) / 2
    439 +        val top = (height - codeSize) / 2
    440 +        for (y in 0 until codeSize) {
    441 +            for (x in 0 until codeSize) {
    442 +                if (matrix.get(x, y)) {
    443 +                    val at = (y + top) * rowStride + (x + left) * pixelStride
    444 +                    plane[at] = 0 // ink
    445 +                }
    446 +            }
    447 +        }
    448 +        return plane
    449 +    }
    450 +
    451 +    /** The analyzer's decoder: zxing over a luminance plane. */
    452 +    private fun decode(luma: ByteArray, width: Int, height: Int): String? {
    453 +        val reader = MultiFormatReader().apply {
    454 +            setHints(
    455 +                mapOf(
    456 +                    DecodeHintType.POSSIBLE_FORMATS to listOf(BarcodeFormat.QR_CODE),
    457 +                    DecodeHintType.CHARACTER_SET to "UTF-8",
    458 +                ),
    459 +            )
    460 +        }
    461 +        val source = PlanarYUVLuminanceSource(
    462 +            luma, width, height, 0, 0, width, height, false,
    463 +        )
    464 +        return try {
    465 +            reader.decodeWithState(BinaryBitmap(HybridBinarizer(source))).text
    466 +        } catch (_: NotFoundException) {
    467 +            null
    468 +        }
    469 +    }
    470 +
    471 +    private fun lumaOf(rowStride: Int, pixelStride: Int = 1) = extractLuma(
    472 +        ByteBuffer.wrap(frame(rowStride, pixelStride)),
    473 +        rowStride, pixelStride, width, height,
    474 +    )
    475 +
    476 +    @Test
    477 +    fun aTightlyPackedFrameDecodes() {
    478 +        assertEquals(payload, decode(lumaOf(width), width, height))
    479 +    }
    480 +
    481 +    @Test
    482 +    fun aFrameWithPaddedRowsDecodes() {
    483 +        // Whether the camera pads, and by how much, is the camera's choice.
    484 +        for (padding in listOf(16, 32, 64, 128)) {
    485 +            val rowStride = width + padding
    486 +            assertEquals(
    487 +                "padding of $padding bytes",
    488 +                payload,
    489 +                decode(lumaOf(rowStride), width, height),
    490 +            )
    491 +        }
    492 +    }
    493 +
    494 +    @Test
    495 +    fun aFrameWithInterleavedSamplesDecodes() {
    496 +        assertEquals(payload, decode(lumaOf(width * 2, pixelStride = 2), width, height))
    497 +    }
    498 +
    499 +    @Test
    500 +    fun copyingAPaddedPlaneWholesaleDoesNotDecode() {
    501 +        // What the analyzer used to do, kept as the reason the code above
    502 +        // exists: one bulk copy of a padded plane shifts every row after the
    503 +        // first, and the decoder then never finds anything at all.
    504 +        val rowStride = width + 32
    505 +        assertNull(decode(frame(rowStride), width, height))
    506 +    }
    507 +
    508 +    @Test
    509 +    fun theCodeIsReadWhicheverWayUpThePhoneIsHeld() {
    510 +        // zxing finds a QR code by its finder patterns and takes the
    511 +        // orientation from them, so the analyzer does not have to rotate the
    512 +        // frame to the upright position first.
    513 +        val upright = lumaOf(width)
    514 +        for (degrees in listOf(0, 90, 180, 270)) {
    515 +            val turned = rotate(upright, width, height, degrees)
    516 +            val w = if (degrees == 90 || degrees == 270) height else width
    517 +            val h = if (degrees == 90 || degrees == 270) width else height
    518 +            assertEquals("rotated by $degrees", payload, decode(turned, w, h))
    519 +        }
    520 +    }
    521 +
    522 +    /** Clockwise rotation of a tightly packed plane, as the sensor would give it. */
    523 +    private fun rotate(plane: ByteArray, width: Int, height: Int, degrees: Int): ByteArray {
    524 +        val out = ByteArray(width * height)
    525 +        for (y in 0 until height) {
    526 +            for (x in 0 until width) {
    527 +                val v = plane[y * width + x]
    528 +                when (degrees) {
    529 +                    90 -> out[x * height + (height - 1 - y)] = v
    530 +                    180 -> out[(height - 1 - y) * width + (width - 1 - x)] = v
    531 +                    270 -> out[(width - 1 - x) * height + y] = v
    532 +                    else -> out[y * width + x] = v
    533 +                }
    534 +            }
    535 +        }
    536 +        return out
    537 +    }
    538 +}