A long time ago I had this question so I looked through some Android code for this. To me, the most expensive part is doing the search through the image given that you don't know where the qr code is or its orientation.

The key is in the finder patterns (mentioned in the article). If you imagine a line cutting through the center area of one and the series of pixel values you get along the line you'll notice that you get a simple symmetric (mostly)White(mostly)BlackWBBBWBW series. These sequences are easy to search for to get a list of finder pattern candidate locations. Rejecting the false positives is a relatively straightforward and local operation, as is refining exactly where the pattern is centered.

With the cleaned up (hopefully short) list of candidate corners you can propose an orientation/scale (technically a homography) to do the necessary sampling to get the rest of the bits. If none of these work out, you ask the user to try take another picture.