[Fire HD 6 and 7 General] bibikalka:
Update5: 4.5.5 is out, and there is no reason NOT to update to 4.5.5. Please use the newer 4.5.5 upgrade instructions in the link below :

http://xdaforums.com/fire-hd/general/upgrade-to-4-5-5-root-t3174449

Another alternative is Lollipop:

http://xdaforums.com/fire-hd/general/how-to-upgrade-to-lollipop-root-gapps-t3163950

And these are the earlier (original) 4.5.x upgrade instructions which require modifying the Amazon update file:

Update4: For users with low computer proficiency (a.k.a "newbies"), DoLooper has written a post trying to make the instructions most accessible :

http://xdaforums.com/showpost.php?p=61832754&postcount=10

If you still have questions after that, post here!

Update3: I've uploaded the 4.5.4 update file to Dropbox, now everything is super simple and you can skip steps 1)-4):

https://www.dropbox.com/s/17ngnhmvnkh1cpx/twrp_ready_update-kindle-20.4.5.4_user_454006120.zip?dl=0

md5sum : ab9468126ee7d7ff0b1c38a96313ef20

Use at your own risk (it works for me!)

If the procedure works for you, don't forget to click "Thanks" ;)

Update2: Thanks to DoLooper, this has been established as the simplest and quickest way to get full GAPPS working. The instructions are simplified further to incorporate suggestions.

Update: Looks like the procedure worked for several people, but there is a single pitfall which appears to be common. I added some additional instructions below in red.

### Original post

I am making a separate topic out of this. Tested this yesterday, going from 4.5.2 to 4.5.4

What you need to have before you proceed : unlocked bootloader (according to reports, not really needed, skip), TWRP and rooted FireOS (4.5.3 or below). Also, download jmz tool to somewhere (can skip this too), and SuperSu flashable zip.

Important: If you have anything other than 4.5.3 right now, I recommend that you flash the 4.5.3 bootloader separately first before doing any updating business. I've attached the flashable zip with 4.5.3 bootloader as well (uboot*zip). The other bootloaders are very risky !!! 4.5.1 and 4.5.2 will not let you into TWRP by the "power" and "vol+" button push if you screw up !!!

0) If you used JMZ tool for GAPPS install or did a manual update prevention, clean up GAPPS update blockers by deleting the following dirs in /data/app (this will make your life easier later on!):

com.android.vending-1.apk

com.android.vending-2.apk

com.google.android.gms-1.apk

com.google.android.gms-2.apk

1) Download the latest 20-4.5.4 update to a PC ( https://kindle-fire-updates.s3.amazonaws.com/update-kindle-20.4.5.4_user_454006120.bin ), rename *bin to *zip, unpack, and replace the attached "updater-script" below in 20-4.5.4/META-INF/com/google/android/updater-script

2) Delete the following directories/files :

a) here you remove stuff you will not flash

20-4.5.4/recovery

20-4.5.4/images

b) here you will remove files to make room in /system to flash bigger GAPPS

20-4.5.4/system/priv-app/com.amazon.weather.apk

20-4.5.4/system/priv-app/moffice_6.0.1_default_en00105_multidex_195423.apk

20-4.5.4/system/priv-app/com.amazon.geo.client.maps.apk

(can delete more if you need space in /system and know what is useless, and a few things could just be moved to /data/app with no issues)

3)Rename (just in case, this will make OTA blocked):

20-4.5.4/system/priv-app/DeviceSoftwareOTA.apk to *apk_

4) Zip everything into update.zip. Make sure the paths in zip are the same as in the original 4.5.4 update from Amazon (QC this carefully!). Put the zip on a USB stick with FAT (if you have an OTG cable). Alternatively, upload it to the device somewhere to the Download folder

Possible pitfall: When you create your update.zip, look into it!!! It should have {system,boot.img,etc} right at the top level, just like the original Amazon update. If you have {yourpath/system, yourpath/boot.img,etc}, you need to re-zip and make sure that "yourpath" is removed.

5) Boot into TWRP, and flash the 4.5.3 bootloader. Reboot. Skip if you already have 4.5.3

6) Boot into TWRP, and flash update.zip from 4) . Then immediately after flash supersu.zip ( https://download.chainfire.eu/396/supersu/ ). Reboot to FireOS. If you choose not to flash supersu.zip here, before you reboot TWRP, it will ask you to root the device, say yes (leaving hooks for later root)

7) Re-boot to TWRP, flash a GAPPS package, such as Pico (Uni) GAPPS for KitKat ( http://www.androidrootz.com/2015/03/download-android-44x-kitkat-pa-gapps.html ). Wipe dalvik/cache and reboot to FireOS (Note: The free room in /system is still kind of limited, either remove more stuff in Step 2), or go with the smaller GAPPS. If you download my update package, you'll probably have about ~140 Mb of room in /system for GAPPS). Wipe dalvik/cache, reboot.

8) In FireOS, install jmz tool, and do small tweaks. Important, installing GAPPS via this tool is obsolete !!! Don't do it!!!. Alternatively, skip this tool, and just do it manually or via the scripts, as per here :

http://xdaforums.com/fire-hd/general/fireos-4-5-x-root-quickly-switch-to-t3145613

The lockscreen ads can be reversibly blocked via this adb command :

adb shell su -c "pm disable com.amazon.kindle.kso/com.amazon.kindle.kso.lockscreen.LockscreenUpdateS ervice"

(as per DoLooper's suggestion)

P.S. 4.5.4 allows the latest GAPPS to work fine, so they will update themselves over time, let them. No need anymore to keep Google Play Services at 7.0.99