How can I get the Bluetooth working on my Lenovo Yoga 3?

As of version 3.19, this device is supported in the Linux kernel, but you need to manually provide the device's firmware to the kernel.

Finding the Firmware:

You can find the firmware in the device's Windows driver, which you can download from Lenovo (or your computer manufacturer's website). Many drivers can just be unzipped, but for this particular computer, the driver is an .exe file and must be extracted with wine.

wine 4ab802rf.exe

Follow the "installation" instructions. The wizard will extract the .exe file and on the last step will ask to install it. Uncheck "Install Broadcom Bluetooth Driver now":

The driver file has been extracted to ~/.wine/driver_c/drivers/Broadcom Bluetooth Driver/

Identifying the right file

In my case, there are 20 - 30 firmware files in the extracted package. Which one corresponds to your device is revealed in one of the driver's inf files. Find your device ID from the output of lsusb or if that's unclear, usb-devices. In this case, it's e07a. Then grep the inf files to find out which one talks about that device:

grep -c E07A -r --include \*.inf
Win32/LD/bcbtumsLD-win7x86.inf:0
Win32/bcmhidnossr.inf:0
Win32/btwl2cap.inf:0
Win32/btwavdt.inf:0
Win32/btwrchid.inf:0
Win32/bcbtums-win8x86-brcm.inf:17
Win32/btwaudio.inf:0
Win64/LD/bcbtumsLD-win7x64.inf:0
Win64/bcmhidnossr.inf:0
Win64/btwl2cap.inf:0
Win64/btwavdt.inf:0
Win64/btwrchid.inf:0
Win64/bcbtums-win8x64-brcm.inf:17
Win64/btwaudio.inf:0
Autorun.inf:0

So in this driver, you can look in either Win32/bcbtums-win8x86-brcm.inf or Win64/bcbtums-win8x64-brcm.inf. Look through the file and find the hex file that is mentioned near E07A:

;;;;;;;;;;;;;RAMUSBE07A;;;;;;;;;;;;;;;;;

[RAMUSBE07A.CopyList]
bcbtums.sys
btwampfl.sys
BCM20702A1_001.002.014.1443.1496.hex

So the fimware is in the same directory and named BCM20702A1_001.002.014.1443.1496.hex.

Converting and Placing the Firmware

Download and compile the hex2hcd tool.

git clone https://github.com/jessesung/hex2hcd.git
cd hex2hcd
make

Convert the firmware to hcd:

hex2hcd BCM20702A1_001.002.014.1443.1496.hex firmware.hcd

Rename and move the firmware to the system's firmware subdirectory:

su -c 'mv firmware.hcd /lib/firmware/brcm/BCM20702A0-0489-e07a.hcd'

The name of this file is critical. The two sets of four characters, in this case 0489-e07a, should match your device's Vendor ID and Product ID.

Loading the Firmware

The easiest way to load the firmware is to power off your computer and turn it on again. Note that the computer should be turned off; a simple reboot may not be sufficient to reload this firmware.

Following drs' using a shortcut, I managed to get the file and got possitive results. My bluetooth devices wasn't able to detect nearby visible devices, but now is.

The shortut I used was that since my computer has no optical drive and has Windows preinstalled, it came with a partition full of drivers. I found a directory with heaps of bluetooth drivers but looking into the INF file that drs suggested, I found that the E07A device was linked to driver file BCM20702A1_001.002.014.1483.1651.hex

After that I compiled de hex2hcd program and converted the file to HCD. I had to preserve BCM20702A1 name part as opposed to replacing it for BCM2070A0, as per the dmesg "patch not found" message.

I have not been able to pair my device, but being able to scan is definitely a step forward.

If you need the HCD file, please message me and hopefully I'll send it to you soon. I'll also send it to linux bluetooth mailing list.

EDIT. Apparently 1651 in the Windows HEX driver filename refers to the build number. Through dmesg I can see the kernel states that 1651 is the build number.